From gap-exponential time hypothesis to fixed parameter tractable inapproximability

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
Date
2020
Major/Subject
Mcode
Degree programme
Language
en
Pages
39
772-810
Series
SIAM JOURNAL ON COMPUTING, Volume 49, issue 4
Abstract
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT) for any computable functions t and f that are independent of N (for Clique, we want f (OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no nontrivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f (OPT)-FPT-approximation algorithm for DomSet for any function f. In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016; P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3 SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the k(o(1))-FPT-approximation algorithm for the Densest k-Subgraph problem.
Description
Keywords
hardness of approximation, parameterized complexity, subexponential-time algorithms, fine-grained complexity, clique, dominating set, DENSE K-SUBGRAPH, LOWER BOUNDS, COMPLEXITY, HARDNESS, INAPPROXIMABILITY, APPROXIMATION, PROOFS
Other note
Citation
Chalermsook , P , Cygan , M , Kortsarz , G , Laekhanukit , B , Manurangsi , P , Nanongkai , D & Trevisan , L 2020 , ' From gap-exponential time hypothesis to fixed parameter tractable inapproximability : Clique, dominating set, and more ' , SIAM JOURNAL ON COMPUTING , vol. 49 , no. 4 , pp. 772-810 . https://doi.org/10.1137/18M1166869