Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Sparsification and subexponential approximationActa Informatica, 2016
- Lower Bounds Based on the Exponential-Time Hypothesis2015
- On Subexponential and FPT-Time InapproximabilityAlgorithmica, 2014
- Parameterized (in)approximability of subset problemsOperations Research Letters, 2014
- The Minimum Feedback Arc Set Problem is NP-Hard for TournamentsCombinatorics, Probability and Computing, 2006
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power qJournal of Combinatorial Theory, Series B, 1994
- Approximations for the maximum acyclic subgraph problemInformation Processing Letters, 1994
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976