Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
From MaRDI portal
Publication:4575659
DOI10.1145/3381426zbMATH Open1410.68281arXiv1508.05282OpenAlexW2228247117WikidataQ130971035 ScholiaQ130971035MaRDI QIDQ4575659
Author name not available (Why is that?)
Publication date: 16 July 2018
Published in: (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1508.05282
No records found.
No records found.
This page was built for publication: Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575659)
