A 9k kernel for nonseparating independent set in planar graphs

作者：Kowalik Lukasz^*; Mucha Marcin

来源：Theoretical Computer Science, 2014, 516: 86-95.

DOI：10.1016/j.tcs.2013.11.021

• Fixed parameter algorithms
• Kemelization
• Planar graphs
• Connected vertex cover
• Nonseparating independent set

We study kernelization (a kind of efficient preprocessing) for NP-hard problems on planar graphs. We focus on the PLANAR MAXIMUM NONSEPARATING INDEPENDENT SET problem, where given a planar graph and an integer k one has to find an independent set of size k whose removal leaves the graph connected. Our main result is a kernel of size at most 9k vertices for this 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 not equal NP. As a by-product we show 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 [12] 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 vertical bar I vertical bar >= 4n - 3 vertical bar C vertical bar.

• 出版日期2014-1-9