A single-exponential FPT algorithm for the K4K4-minor cover problem

• We provide an efficient FPT algorithm for the K4K4-minor cover problem.
• It combines iterative compression with protrusion reduction and branching.
• It extends previous algorithms for Vertex Cover and Feedback Vertex Set.

Given a graph G   and a parameter k∈Nk∈N, the parameterized K4K4-minor cover problem asks whether at most k vertices can be deleted to turn G   into a K4K4-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-tVertex Deletion problems: t=0t=0 for Vertex Cover and t=1t=1 for Feedback Vertex Set. While single-exponential FPT algorithms, i.e. running in 2O(k)⋅nO(1)2O(k)⋅nO(1) time, are known for these two latter problems, it was open whether the K4K4-minor cover problem could be solved in single-exponential FPT time. This paper answers this question in the affirmative. Observe that it is known to be unlikely that Treewidth-tVertex Deletion can be solved in time 2o(k)⋅nO(1)2o(k)⋅nO(1).