Interval completion is Fixed Parameter Tractable

Yngve Villanger 1 Pinar Heggernes 1 Christophe Paul 2 Jan Arne Telle 1
2 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371876
Contributor : Isabelle Gouat <>
Submitted on : Monday, March 30, 2009 - 4:27:46 PM
Last modification on : Thursday, February 7, 2019 - 2:28:14 PM

Links full text

Identifiers

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. ⟨10.1137/070710913⟩. ⟨lirmm-00371876⟩

Share

Metrics

Record views

227