Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
On the Hardness of Losing Width
verfasst von : Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Aktivieren 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
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
$\eta \slash \rho$
-
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
$\eta \slash \rho$
-
transversal
parameterized
by the size of
X
. We show that for every fixed
η
and
ρ
that either satisfy 1 ≤
η
<
ρ
, or
η
= 0 and 2 ≤
ρ
, the
$\eta \slash \rho$
-
transversal
problem does not admit a polynomial kernel unless
$\textrm{NP} \subseteq \textrm{coNP}/\textrm{poly}$
. This resolves an open problem raised by Bodlaender and Jansen in [STACS 2011]. Finally, we complement our kernelization lower bounds by showing that
$\rho \slash 0$
-
transversal
admits a polynomial kernel for any fixed
ρ
.