  In this work, we focus on several completion problems for subclasses of
chordal graphs: Minimum Fill-In, Interval Completion, Proper Interval
Completion, 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
2^O(n^(1/2) / log^c n) or 2^O(k^(1/4) / log^c k) n^O(1), 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(sqrt(k)) n^O(1).
  For all the aforementioned completion problems, apart from Proper Interval
Completion, FPT algorithms with running time of the form 2^O(sqrt(k) log k)
n^O(1) are known. Thus, the second result proves that a significant improvement
of any of these algorithms would lead to a surprising breakthrough in the
design of approximation algorithms for Min Bisection.
  To prove our results, we use a reduction methodology based on combining the
classic approach of starting with a sparse instance of 3-Sat, prepared using
the Sparsification Lemma, with the existence of almost linear-size
Probabilistically Checkable Proofs (PCPs). Apart from our main results, we also
obtain lower bounds excluding the existence of subexponential algorithms for
the Optimum Linear Arrangement problem, as well as improved, yet still not
tight, lower bounds for Feedback Arc Set in Tournaments.
