• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Subexponential Parameterized Algorithm for Interval Completion

ACM Transactions on Algorithms. 2018. Vol. 14. No. 3. P. 1-62.
Bliznets Ivan, Fomin F., Pilipczuk M., Pilipczuk M.

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 kedge 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 et al. [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger et al. [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 kO(&sqrt;k)nO(1). This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.