2015/08/21 by Ivan Bliznets, Marek Cygan, Bliznets, Ivan +9
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1508.05282
Accepted to SODA 2016
openalex publication_date 2015/08/21 · arxiv created 2015/10/15 · arxiv updated 2015/10/16 · openalex created_date 2022/10/03 · openalex updated_date 2026/08/01
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(n^(1/2) / logc n) or 2O(k^(1/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(sqrt(k)) nO(1). For all the aforementioned completion problems, apart from Proper Interval Completion, FPT algorithms with running time of the form 2O(sqrt(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 (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.