### Book chapter

## Subexponential parameterized algorithm for Interval Completion

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*(*k*2*k**n*3*m*). We give the first subexponential parameterized algorithm solving Interval Completion in time *k**O*([EQUATION])*n**O*(1). This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.