A Quartic Kernel for Pathwidth-One Vertex Deletion

Details A Quartic Kernel for Pathwidth-One Vertex Deletion A Quartic Kernel for Pathwidth-One Vertex Deletion

2010-09-04

arxiv.org/abs/1009.0806v1

Computer Science

Data Structures and Algorithms

Full version of an extended abstract accepted for publication in the proceedings of WG 2010. 18 pages, 1 figure

Scientific paper

The pathwidth of a graph is a measure of how path-like the graph is. Given a graph G and an integer k, the problem of finding whether there exist at most k vertices in G whose deletion results in a graph of pathwidth at most one is NP- complete. We initiate the study of the parameterized complexity of this problem, parameterized by k. We show that the problem has a quartic vertex-kernel: We show that, given an input instance (G = (V, E), k); |V| = n, we can construct, in polynomial time, an instance (G', k') such that (i) (G, k) is a YES instance if and only if (G', k') is a YES instance, (ii) G' has O(k^{4}) vertices, and (iii) k' \leq k. We also give a fixed parameter tractable (FPT) algorithm for the problem that runs in O(7^{k} k \cdot n^{2}) time.

Affiliated with

Also associated with

No associations

Rating

A Quartic Kernel for Pathwidth-One Vertex Deletion 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 A Quartic Kernel for Pathwidth-One Vertex Deletion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Quartic Kernel for Pathwidth-One Vertex Deletion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284571