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 :
Article dans une revue
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2009, 38 (5), pp.2007-2020. 〈http://link.aip.org/link/?SMJ/38/2007〉. 〈10.1137/070710913〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371876
Contributeur : Isabelle Gouat <>
Soumis le : lundi 30 mars 2009 - 16:27:46
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle. Interval completion is Fixed Parameter Tractable. SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2009, 38 (5), pp.2007-2020. 〈http://link.aip.org/link/?SMJ/38/2007〉. 〈10.1137/070710913〉. 〈lirmm-00371876〉

Partager

Métriques

Consultations de la notice

172