Polynomial kernels for Proper Interval Completion and related problems

14 years 10 months ago

Download www.lirmm.fr

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 × V ) \ E such that the graph H = (V, E ∪F) is a proper interval graph. The Proper Interval Completion problem ﬁnds applications in molecular biology and genomic research [14, 22]. First announced by Kaplan, Tarjan and Shamir in FOCS ’94, this problem is known to be FPT [14], 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(k5 ) vertices. Moreover, we prove that a related problem, the so-called Bipartite Chain Deletion problem, admits a kernel with at most O(k2 ) vertices, completing a previous result of Guo [12].

Stéphane Bessy, Anthony Perez

Real-time Traffic