Skip to Main content Skip to Navigation
Conference papers

Polynomial Kernels for Proper Interval Completion and Related Problems

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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738226
Contributor : Stéphane Bessy <>
Submitted on : Wednesday, October 3, 2012 - 5:43:09 PM
Last modification on : Thursday, July 19, 2018 - 11:54:04 AM
Long-term archiving on: : Friday, January 4, 2013 - 3:59:13 AM

File

pic.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00738226, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

347

Files downloads

429