Advertisement
Published in:
2012 | OriginalPaper | Chapter
A 9k Kernel for Nonseparating Independent Set in Planar Graphs
Authors : Łukasz Kowalik, Marcin Mucha
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. Our main result is a kernel of size at most 9
k
vertices for the
Planar Maximum Nonseparating Independent Set
problem. A direct consequence of this result is that
Planar Connected Vertex Cover
has no kernel with at most 9/8
k
vertices, assuming
P
≠
NP
. We also show a very simple 5
k
-vertices kernel for
Planar Max Leaf
, which results in a lower bound of 5/4
k
vertices for the kernel of
Planar Connected Dominating Set
(also under
P
≠
NP
).