2012 | OriginalPaper | Buchkapitel
Nonblocker in H-Minor Free Graphs: Kernelization Meets Discharging
verfasst von : Łukasz Kowalik
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
Perhaps the best known kernelization result is the kernel of size 335
k
for the
Planar Dominating Set
problem by Alber et al. [1], later improved to 67
k
by Chen et al. [5]. This result means roughly, that the problem of finding the smallest dominating set in a planar graph is easy when the optimal solution is small. On the other hand, it is known that
Planar Dominating Set
parameterized by
k
′ = |
V
| −
k
(also known as
Planar Nonblocker
) has a kernel of size 2
k
′. This means that
Planar Dominating Set
is easy when the optimal solution is very large. We improve the kernel for
Planar Nonblocker
to
$\frac{7}{4}k'$
. This also implies that
Planar Dominating Set
has no kernel of size at most
$(\frac{7}{3}-\epsilon)k$
, for any
ε
> 0, unless
P
=
NP
. This improves the previous lower bound of (2 −
ε
)
k
of [5]. Both of these results immediately generalize to
H
-minor free graphs (without changing the constants).
In our proof of the bound on the kernel size we use a variant of the
discharging method
(used e.g. in the proof of the four color theorem). We give some arguments that this method is natural in the context of kernelization and we hope it will be applied to get improved kernel size bounds for other problems as well.
As a by-product we show a result which might be of independent interest: every
n
-vertex graph with no isolated vertices and such that every pair of degree 1 vertices is at distance at least 5 and every pair of degree 2 vertices is at distance at least 2 has a dominating set of size at most
$\frac{3}7n$
.