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].
Type de document :
Communication dans un congrès
Fundamentals of Computation Theory 2011, Norway. pp.229-239, 2011, LNCS
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00738226
Contributeur : Stéphane Bessy <>
Soumis le : mercredi 3 octobre 2012 - 17:43:09
Dernière modification le : jeudi 19 juillet 2018 - 11:54:04
Document(s) archivé(s) le : vendredi 4 janvier 2013 - 03:59:13

Fichier

pic.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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, 2011, LNCS. 〈lirmm-00738226〉

Partager

Métriques

Consultations de la notice

116

Téléchargements de fichiers

198