On the Hardness of Losing Width

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