Anzeige
Erschienen in:
01.01.2014
On the Hardness of Losing Width
Erschienen in: Theory of Computing Systems | Ausgabe 1/2014
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
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 ρ.