In this work, we focus on several completion problems for subclasses of chordal graphs: M INIMUM F ILL -I N , I NTERVAL C OMPLETION , P ROPER I NTERVAL C OMPLETION , T RIVIALLY P ERFECT C OMPLETION , and T HRESHOLD C OMPLETION . In these problems, the task is to add at most k edges to a given graph 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 C HAIN C OMPLETION 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 M IN B ISECTION on d -regular graphs, for some constant d , none of these problems can be solved in time 2 o ( n ) or 2 o √k) }· n O (1) . For all the aforementioned completion problems, apart from P ROPER I NTERVAL C OMPLETION , FPT algorithms with running time of the form 2 O (√ 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 M IN B ISECTION . To prove our results, we use a reduction methodology based on combining the classic approach of starting with a sparse instance of 3-S AT , prepared using the Sparsification Lemma, with the existence of almost linear-size Probabilistically Checkable Proofs. Apart from our main results, we also obtain lower bounds excluding the existence of subexponential algorithms for the O PTIMUM L INEAR A RRANGEMENT problem, as well as improved, yet still not tight, lower bounds for F EEDBACK A RC S ET IN T OURNAMENTS .

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 2O(n1/2/logcn) or 2O(k1/4/logck). nO(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 2o(n) or .