Lower Bounds for the Parameterized Complexity of Minimum Fill-in and Other Completion Problems

ACM Transactions on Algorithms. 2020. Vol. 16. No. 2. P. 1–31.

Bliznets I., Cygan M., Komosa P., Pilipczuk M., Lukas M.

In this work, we focus on several completion problems for subclasses of chordal graphs: MINIMUM FILL-IN, INTERVAL COMPLETION, PROPER INTERVAL COMPLETION, TRIVIALLY PERFECT COMPLETION, and THRESHOLD COMPLETION. 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 CHAIN COMPLETION problem:

• Assuming the Exponential Time Hypothesis, none of these problems can be solved in time 2O(n1/2/logc n) or 2O(k1/4/logc k)· 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 2o√k)}· nO(1).

For all the aforementioned completion problems, apart from PROPER INTERVAL COMPLETION, FPT algorithms with running time of the form 2O(√k log k)· nO(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. 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.

Keywords: lower bounds, chordal completion, minimum fill-in, нижнее оценки, реберное дополнение