Structural Parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization

摘要

A feedback vertex set in an undirected graph is a subset of vertices whose removal results in an acyclic graph. We consider the parameterized and kernelization complexity of feedback vertex set where the parameter is the size of some structure in the input. In particular, we consider parameterizations where the parameter is (instead of the solution size), the distance to a class of graphs where the problem is polynomial time solvable, and sometimes smaller than the solution size. Here, by distance to a class of graphs, we mean the minimum number of vertices whose removal results in a graph in the class. Such a set of vertices is also called the ‘deletion set’. In this paper, we show that FVS is fixed-parameter tractable by an $${{mathcal {O}}}(2^k n^{{{mathcal {O}}}(1)})$$ O ( 2 k n O ( 1 ) ) time algorithm, but is unlikely to have polynomial kernel when parameterized by the number of vertices of the graph whose degree is at least 4. This answers a question asked in an earlier paper. We also show that an algorithm with running time $${{mathcal {O}}}((sqrt{2} - epsilon )^k n^{{{mathcal {O}}}(1)})$$ O ( ( 2 - ϵ ) k n O ( 1 ) ) is not possible unless SETH fails. When parameterized by k , the number of vertices, whose deletion results in a split graph, we give an $${{mathcal {O}}}(3.148^k n^{{{mathcal {O}}}(1)})$$ O ( 3 . 148 k n O ( 1 ) ) time algorithm. When parameterized by k , the number of vertices whose deletion results in a cluster graph (a disjoint union of cliques), we give an $${{mathcal {O}}}(5^k n^{{{mathcal {O}}}(1)})$$ O ( 5 k n O ( 1 ) ) algorithm. Regarding kernelization results, we show that When parameterized by k , the number of vertices, whose deletion results in a pseudo-forest, FVS has an $${{mathcal {O}}}(k^7)$$ O ( k 7 ) vertices kernel improving from the previously known $${{mathcal {O}}}(k^{10})$$ O ( k 10 ) bound. When parameterized by the number k of vertices, whose deletion results in a mock- d -forest, we give a kernel with $${{mathcal {O}}}(k^{3d+3})$$ O ( k 3 d + 3 ) vertices. We also prove a lower bound of $$varOmega (k^{d+2})$$ Ω ( k d + 2 ) size (under complexity theoretic assumptions). Mock-forest is a graph where each vertex is contained in at most one cycle. Mock- d -forest for a constant d is a mock-forest where each component has at most d cycles.