Subexponential parameterized algorithm for Interval Completion
Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, Michał Pilipczuk · 2015
In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of Interval Completion was asked by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O(k2kn3m). We give the first subexponential parameterized algorithm solving Interval Completion in time . This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.