Interval completion with few edges

We present an algorithm with runtime O(k (2k) n 3 * 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.

Authors

• Pinar Heggernes
• Christophe Paul
• Jan Arne Telle
• Yngve Villanger

Keywords

• FPT algorithm
• branching
• edge completion
• interval graphs
• physical mapping
• profile minimization