On the Hardness of Losing Width

Abstract

Let η ≥ 0 be an integer and G be a graph. A set X ⊆ V(G) is called a η-transversal in G if G ∖ X has treewidth at most η. Note that a 0-transversal is a vertex cover, while a 1-transversal is a feedback vertex set of G. In the η\slashρ -transversal problem we are given an undirected graph G, a ρ-transversal X ⊆ V(G) in G, and an integer ℓ and the objective is to determine whether there exists an η-transversal Z ⊆ V(G) in G of size at most ℓ. In this paper we study the kernelization complexity of η\slashρ -transversal parameterized by the size of X. We show that for every fixed η and ρ that either satisfy 1 ≤ η < ρ, or η = 0 and 2 ≤ ρ, the η\slashρ -transversal problem does not admit a polynomial kernel unless NP⊆coNP/poly . This resolves an open problem raised by Bodlaender and Jansen in [STACS 2011]. Finally, we complement our kernelization lower bounds by showing that ρ\slash0 -transversal admits a polynomial kernel for any fixed ρ.