Polynomial kernels for Proper Interval Completion and related problems

Details Polynomial kernels for Proper Interval Completion and related problems Polynomial kernels for Proper Interval Completion and related problems

2011-03-29

arxiv.org/abs/1103.5599v2

Computer Science

Data Structures and Algorithms

Scientific paper

Given a graph G = (V,E) and a positive integer k, the Proper Interval Completion problem asks whether there exists a set F of at most k pairs of (V \times V)\E such that the graph H = (V,E \cup F) is a proper interval graph. The Proper Interval Completion problem finds applications in molecular biology and genomic research. First announced by Kaplan, Tarjan and Shamir in FOCS '94, this problem is known to be FPT, but no polynomial kernel was known to exist. We settle this question by proving that Proper Interval Completion admits a kernel with at most O(k^5) vertices. Moreover, we prove that a related problem, the so-called Bipartite Chain Deletion problem, admits a kernel with at most O(k^2) vertices, completing a previous result of Guo.

Affiliated with

Also associated with

No associations

Rating

Polynomial kernels for Proper Interval Completion and related problems 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 Polynomial kernels for Proper Interval Completion and related problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial kernels for Proper Interval Completion and related problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-163159