Interval completion with few edges
Pinar Heggernes, Christophe Paul, Jan Arne Telle, Yngve Villanger · 2007
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.