Interval completion is Fixed Parameter Tractable

Abstract : We present an algorithm with runtime $O(k^{2k}n^3m)$ for the following NP-complete problem: Given an arbitrary graph $G$ on $n$ vertices and $m$ edges, can we obtain an interval graph by adding at most $k$ new edges to $G$? This resolves the long-standing open question, first posed by Kaplan, Shamir and Tarjan, of whether this problem could be solved in time $f(k).n^{O(1)}$. The problem has applications in Physical Mapping of DNA and in Profile Minimization for Sparse Matrix Computations. For the first application, our results show tractability for the case of a small number $k$ of false negative errors, and for the second, a small number $k$ of zero elements in the envelope. Our algorithm performs bounded search among possible ways of adding edges to a graph to obtain an interval graph, and combines this with a greedy algorithm when graphs of a certain structure are reached by the search. The presented result is surprising, as it was not believed that a bounded search tree algorithm would suffice to answer the open question affirmatively.
Type de document :
[Research Report] RR-06058, Lirmm. 2007
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Christophe Paul <>
Soumis le : lundi 20 novembre 2006 - 20:05:20
Dernière modification le : jeudi 11 janvier 2018 - 06:26:13
Document(s) archivé(s) le : mardi 6 avril 2010 - 19:17:48



  • HAL Id : lirmm-00115278, version 1



Christophe Paul, Jan Arne Telle, Yngve Villanger, Pinar Heggerness. Interval completion is Fixed Parameter Tractable. [Research Report] RR-06058, Lirmm. 2007. 〈lirmm-00115278〉



Consultations de la notice


Téléchargements de fichiers