Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949508 | Discrete Applied Mathematics | 2017 | 6 Pages |
Abstract
One of the core technical contributions of the work of Jansen, Lokshtanov, and Saurabh is an algorithm that solves a weighted variant of Vertex Planarization in time 2O(wlogw)â
n on graphs of treewidth w. In this short note we prove that the running time of this routine is tight under the Exponential Time Hypothesis, even in unweighted graphs and when parameterizing by treedepth. Consequently, it is unlikely that a potential single-exponential algorithm for Vertex Planarization parameterized by the solution size can be obtained by merely improving upon the aforementioned bounded treewidth subroutine.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Marcin Pilipczuk,