Interval Completion with Few Edges

Abstract : We present an algorithm with runtime O(k(2k)n3 * m) 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 :
Communication dans un congrès
STOC'07: 39th ACM Symposium on Theory of Computing, Jun 2007, San Diego, CA, United States. pp.374-381, 2007, 〈10.1145/1250790.1250847〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00189511
Contributeur : Christophe Paul <>
Soumis le : mercredi 21 novembre 2007 - 10:55:40
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Collections

Citation

Pinar Heggerness, Christophe Paul, Jan Arne Telle, Yngve Villanger. Interval Completion with Few Edges. STOC'07: 39th ACM Symposium on Theory of Computing, Jun 2007, San Diego, CA, United States. pp.374-381, 2007, 〈10.1145/1250790.1250847〉. 〈lirmm-00189511〉

Partager

Métriques

Consultations de la notice

53