Polynomial Kernels for Proper Interval Completion and Related Problems - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2011

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].
Fichier principal
Vignette du fichier
pic.pdf (400.57 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00738226 , version 1 (03-10-2012)

Identifiers

  • HAL Id : lirmm-00738226 , version 1

Cite

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⟩
178 View
347 Download

Share

More