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

DOI10.1007/978-3-642-31155-0_11MaRDI QIDQ2904548zbMATH OpenOpenAlexFDO

Authors Eun Jung Kim, Christophe Paul, Geevarghese Philip

Publication date 14 August 2012

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

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

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)

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.

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

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)