We show an algorithm that, given an n -vertex graph G and a parameter k , in time 2 O ( k log k ) n O (1) finds a tree decomposition of G with the following properties: — every adhesion of the tree decomposition is of size at most k , and — every bag of the tree decomposition is ( i , i )-unbreakable in G for every 1 ⩽ i ⩽ k . Here, a set X ⊆ V ( G ) is ( a , b )-unbreakable in G if for every separation ( A , B ) of order at most b in G , we have | A \cap X | ⩽ a or | B ∩ X | ⩽ a . The resulting tree decomposition has arguably best possible adhesion size bounds and unbreakability guarantees. Furthermore, the parametric factor in the running time bound is significantly smaller than in previous similar constructions. These improvements allow us to present parameterized algorithms for M INIMUM B ISECTION , S TEINER C UT , and S TEINER M ULTICUT with improved parameteric factor in the running time bound. The main technical insight is to adapt the notion of lean decompositions of Thomas and the subsequent construction algorithm of Bellenbaum and Diestel to the parameterized setting.

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 .

The H-free Edge Deletion problem asks, for a given graph G and integer k, whether it is possible to delete at most k edges from G to make it H-free, that is, not containing H as an induced subgraph. The H-free Edge Completion problem is defined similarly, but we add edges instead of deleting them. The study of these two problem families has recently been the subject of intensive studies from the point of view of parameterized complexity and kernelization. In particular, it was shown that the problems do not admit polynomial kernels (under plausible complexity assumptions) for almost all graphs H, with several important exceptions occurring when the class of H-free graphs exhibits some structural properties. In this work we complement the parameterized study of edge modification problems to H-free graphs by considering their approximability. We prove that whenever H is 3-connected and has at least two non-edges, then both H-free Edge Deletion and H-free Edge Completion are very hard to approximate: they do not admit poly(OPT)-approximation in polynomial time, unless P=NP, or even in time subexponential in OPT, unless the Exponential Time Hypothesis fails. The assumption of the existence of two non-edges appears to be important: we show that whenever H is a complete graph without one edge, then H-free Edge Deletion is tightly connected to the \minhorn problem, whose approximability is still open. Finally, in an attempt to extend our hardness results beyond 3-connected graphs, we consider the cases of H being a path or a cycle, and we achieve an almost complete dichotomy there.

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 .