Parameter Ecology for Feedback Vertex Set  

作　　者：Bart M.P.Jansen Venkatesh Raman Martin Vatshelle 

机构地区：[1]the Department of Informatics, University of Bergen, 5005 Bergen, Norway [2]the Institute of Mathematical Sciences, Chennai, India

出　　处：《Tsinghua Science and Technology》2014年第4期387-409,共23页清华大学学报（自然科学版（英文版）

基　　金：supported by the European Research Council through Starting Grant 306992 "Parameterized Approximation"

摘　　要：This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.

关 键 词：feedback vertex set parameterized complexity parameter ecology program structural parameterizations kernelization 

分 类 号：O157.5[理学—数学] X24[理学—基础数学]