Can I read Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems on EtoBox?

Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems by Bliznets, Ivan; Cygan, Marek; Komosa, Pawel; Mach, Lukas; Pilipczuk, Michal is a scholarly article available to read on EtoBox.

What is Lower bounds for the parameterized complexity of Minimum Fill-in and other completion problems about?

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 approxim

Author

Bliznets, Ivan; Cygan, Marek; Komosa, Pawel; Mach, Lukas; Pilipczuk, Michal

Published

2015

Language

EN