Room 327

Structural Parameterizations of FVS

Diptapriyo Majumdar

IMSc Chennai

Abstract: A feedback vertex set in an undirected graph is a subset of
vertices whose removal results in an acyclic graph. It is well known that
this problem is NP-Complete in general graph, but polynomial time solvable
in (sub)cubic graph, in pseudo-forests (graphs where every component has at
most one cycle) and mock-forests (graphs where every vertex is part of at
most one cycle). In paramterized complexity, when it is parameterized by
solution size (k), then it has a Fixed-Parameter Algorithm with running
time O(3.619^k.n^{O(1)}) and a kernel with O(k^2) vertices and edges. We
consider the parameterized complexity of feedback vertex set with respect
to the structure of the input. In particular, we show that
-- Feedback Vertex Set is Fixed Parameter Tractable, but is unlikely to
have polynomial kernel when it is parameterized by the number of vertices
of the graph whose degree is more than 3.
-- When parameterized by k, the number of vertices, whose deletion results
in a pseudoforest, we give a kernel consisting of O(k^6) vertices. This
improves the previous known upper bound of O(k^10) kernel.
-- When parameterized by k, the number of vertices whose removal results in
a graph which is a mock-forest but every component has at most d cycles for
some constant d, we give a kernel consisting of O(k^{3d + 3}) vertices and
a kernel lower bound of \Omega(k^{d + 2}) vertices unless NP \subseteq
coNP/poly.