A 9k kernel for nonseparating independent set in planar graphs

DOI10.1016/J.TCS.2013.11.021MaRDI QIDQ385964zbMATH OpenOpenAlexFDO

Authors Łukasz Kowalik, Marcin Mucha

Publication date 13 December 2013

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1207.4666

zbMATH Keywords

connected vertex coverfixed parameter algorithmskernelizationnonseparating independent setplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 9k 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 - epsilon)k vertices, for any epsilon > 0, assuming P

e NP. We also show a very simple 5k-vertices kernel for Planar Max Leaf, which results in a lower bound of (5/4 - epsilon)k vertices for the kernel of Planar Connected Dominating Set (also under P

e NP). As a by-product we show a few extremal graph theory results which might be of independent interest. We prove that graphs that contain no separator consisting of only degree two vertices contain (a) a spanning tree with at least n/4 leaves and (b) a nonseparating independent set of size at least n/9 (also, equivalently, a connected vertex cover of size at most 8/9n). The result (a) is a generalization of a theorem of Kleitman and West [SIDMA 1991] who showed the same bound for graphs of minimum degree three. Finally we show that every n-vertex outerplanar graph contains an independent set I and a collection of vertex-disjoint cycles C such that 9|I| >= 4n-3|C|.

Recommendations

• A \(9k\) kernel for nonseparating independent set in planar graphs
• Towards optimal kernel for connected vertex cover in planar graphs
• Nonblocker in H-minor free graphs: kernelization meets discharging
• Planar graph vertex partition for linear problem kernels
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs

Cites work

• Bidimensionality and kernels
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• FPT algorithms for connected feedback vertex set
• Kernel(s) for problems with no kernel
• Kernelization -- preprocessing with a guarantee
• Kernelization for maximum leaf spanning tree with positive vertex weights
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs
• Linear problem kernels for planar graph problems with small distance property
• Maximum genus and maximum nonseparating independent set of a 3-regular graph
• On feedback vertex sets and nonseparating independent sets in cubic graphs
• On the nonseparating independent set problem and feedback set problem for graphs with no vertex degree exceeding three
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Polynomial-time data reduction for dominating set
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Spanning Trees with Many Leaves
• Subexponential parameterized algorithms on bounded-genus graphs and H-minor-free graphs
• The Rectilinear Steiner Tree Problem is NP-Complete
• Towards optimal kernel for connected vertex cover in planar graphs

Cited in

(3)

• Towards optimal kernel for connected vertex cover in planar graphs
• Extension and its price for the connected vertex cover problem
• A \(9k\) kernel for nonseparating independent set in planar graphs

This page was built for publication: A \(9k\) kernel for nonseparating independent set in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q385964)