Résumé
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 ) nE 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 [16, 24]. First announced by Kaplan, Tarjan and Shamir in FOCS '94, this problem is known to be FPT [16], 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(k3) 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 [13].