A tight lower bound for vertex planarization on graphs of bounded treewidth

DOI10.1016/J.DAM.2016.05.019MaRDI QIDQ2403808zbMATH OpenOpenAlexFDO

Authors Marcin Pilipczuk

Publication date 12 September 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08283

zbMATH Keywords

exponential time hypothesisfixed-parameter tractabilitytreewidthvertex planarization

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: In the Vertex Planarization problem one asks to delete the minimum possible number of vertices from an input graph to obtain a planar graph. The parameterized complexity of this problem, parameterized by the solution size (the number of deleted vertices) has recently attracted significant attention. The state-of-the-art algorithm of Jansen, Lokshtanov, and Saurabh [SODA 2014] runs in time $2^{O(klogk)}cdotn$ on $n$-vertex graph with a solution of size $k$. It remains open if one can obtain a single-exponential dependency on $k$ in the running time bound. 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 $2^{O(wlogw)}cdotn$ 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.

Recommendations

• A near-optimal planarization algorithm
• Tight running time lower bounds for vertex deletion problems
• Obtaining a Planar Graph by Vertex Deletion

Cites work

• A near-optimal planarization algorithm
• Efficient Planarity Testing
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• Lower bounds based on the exponential time hypothesis
• Obtaining a planar graph by vertex deletion
• On search, decision, and the efficiency of polynomial-time algorithms
• Parameterized algorithms
• Planarity Allowing Few Error Vertices in Linear Time
• Sparsity. Graphs, structures, and algorithms
• The node-deletion problem for hereditary properties is NP-complete
• Tree-depth, subgraph coloring and homomorphism bounds
• What's next? Future directions in parameterized complexity
• Which problems have strongly exponential complexity?

Cited in

(16)

• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Orthogonal planarity testing of bounded treewidth graphs
• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Deleting vertices to graphs of bounded genus
• Obtaining a Planar Graph by Vertex Deletion
• scientific article; zbMATH DE number 6868519 (Why is no real title available?)
• Tight running time lower bounds for vertex deletion problems
• Hitting forbidden induced subgraphs on bounded treewidth graphs
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Hitting minors on bounded treewidth graphs. I: General upper bounds
• A near-optimal planarization algorithm
• Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm
• Tight bounds for chordal/interval vertex deletion parameterized by treewidth
• Tree decompositions meet induced matchings: beyond max weight independent set
• Tree decompositions meet induced matchings: beyond max weight independent set
• Sparse induced subgraphs in P₇-Free graphs of bounded clique number

This page was built for publication: A tight lower bound for vertex planarization on graphs of bounded treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403808)