# Interval completion is Fixed Parameter Tractable

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.
Keywords :
Document type :
Journal articles

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00371876
Contributor : Isabelle Gouat Connect in order to contact the contributor
Submitted on : Monday, March 30, 2009 - 4:27:46 PM
Last modification on : Friday, October 22, 2021 - 3:07:29 PM

### 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⟩

Record views