Abstract
Given an input graph G and an integer k, the parameterized K4 -minor cover problem asks whether there is a set S of at most k vertices whose deletion results in a K4 -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 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 co ( k ) nO (1) , it was open whether the K4 -minor cover could be solved in single-exponential FPT time, i.e. in ck nO (1) time.