2012/04/06 by Kim, Eun Jung, Paul, Christophe, Philip, Geevarghese · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1204.1417
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 problem could be solved in single-exponential FPT time, i.e. in ck.nO(1) time. This paper answers this question in the affirmative.