A single-exponential FPT algorithm for the K _4-minor cover problem

DOI10.1007/978-3-642-31155-0_11zbMATH Open1357.68288arXiv1204.1417OpenAlexW2570024161MaRDI QIDQ2904548FDOQ2904548

Authors: Eun Jung Kim, Christophe Paul, Geevarghese Philip 

Publication date: 14 August 2012

Published in: Algorithm Theory – SWAT 2012 (Search for Journal in Brave)

Abstract: Given an input graph G and an integer k, the parameterized K_4-minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K_4-minor-free graph, or equivalently in a graph of treewidth at most 2. This problem is inspired by two well-studied parameterized vertex deletion problems, Vertex Cover and Feedback Vertex Set, which can also be expressed as Treewidth-t Vertex Deletion problems: t=0 for Vertex Cover and t=1 for Feedback Vertex Set. While a single-exponential FPT algorithm has been known for a long time for extsc{Vertex Cover}, such an algorithm for Feedback Vertex Set was devised comparatively recently. While it is known to be unlikely that Treewidth-t Vertex Deletion can be solved in time c^{o(k)}.n^{O(1)}, it was open whether the K_4-minor cover problem could be solved in single-exponential FPT time, i.e. in c^k.n^{O(1)} time. This paper answers this question in the affirmative.

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

Recommendations

• A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
• Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
• Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
• Hitting forbidden minors: approximation and kernelization
• An \(O^\ast ( 2 . 61 9^k )\) algorithm for 4-path vertex cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Cited In (1)

• A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem

This page was built for publication: A single-exponential FPT algorithm for the \(K _{4}\)-minor cover problem

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