Towards optimal kernel for connected vertex cover in planar graphs

Details Towards optimal kernel for connected vertex cover in planar graphs Towards optimal kernel for connected vertex cover in planar graphs

2011-10-10

arxiv.org/abs/1110.1964v1

Computer Science

Data Structures and Algorithms

Scientific paper

We study the parameterized complexity of the connected version of the vertex cover problem, where the solution set has to induce a connected subgraph. Although this problem does not admit a polynomial kernel for general graphs (unless NP is a subset of coNP/poly), for planar graphs Guo and Niedermeier [ICALP'08] showed a kernel with at most 14k vertices, subsequently improved by Wang et al. [MFCS'11] to 4k. The constant 4 here is so small that a natural question arises: could it be already an optimal value for this problem? In this paper we answer this quesion in negative: we show a (11/3)k-vertex kernel for Connected Vertex Cover in planar graphs. We believe that this result will motivate further study in search for an optimal kernel.

Affiliated with

Also associated with

No associations

Rating

Towards optimal kernel for connected vertex cover in planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Towards optimal kernel for connected vertex cover in planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards optimal kernel for connected vertex cover in planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-146747