### Book chapter

## Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems

In this work, we focus on several completion problems for subclasses of chordal graphs: Minimum Fill-In, Interval Completion, Proper IntervalCompletion, Threshold Completion, and Trivially Perfect Completion. In these problems, the task is to add at most *k* edges to a given graph in order to obtain a chordal, interval, proper interval, threshold, or trivially perfect graph, respectively. We prove the following lower bounds for all these problems, as well as for the related Chain Completion problem:

• Assuming the Exponential Time Hypothesis, none of these problems can be solved in time [EQUATION] or [EQUATION], (for some integer *c*.

• Assuming the non-existence of a subexponential-time approximation scheme for Min Bisection on *d*-regular graphs, for some constant *d*, none of these problems can be solved in time 2*o*(*n*) or 2*o*([EQUATION]) · *n**O*(1).

The second result is an evidence, that a significant improvement of the best known algorithms for parameterized completion problems would lead to a surprising breakthrough in the design of approximation algorithms for Min Bisection.