Skip to Main content Skip to Navigation
New interface
Conference papers

Polynomial Kernels for Proper Interval Completion and Related Problems

Stéphane Bessy 1 Anthony Perez 2 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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].
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Stéphane Bessy Connect in order to contact the contributor
Submitted on : Wednesday, October 3, 2012 - 5:43:09 PM
Last modification on : Thursday, October 13, 2022 - 8:24:01 AM
Long-term archiving on: : Friday, January 4, 2013 - 3:59:13 AM


Files produced by the author(s)


  • HAL Id : lirmm-00738226, version 1



Stéphane Bessy, Anthony Perez. Polynomial Kernels for Proper Interval Completion and Related Problems. Fundamentals of Computation Theory 2011, Norway. pp.229-239. ⟨lirmm-00738226⟩



Record views


Files downloads