From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More

Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, Luca Trevisan

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

57 Sitaatiot (Scopus)


We consider questions that arise from the intersection between theareas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [Marx, 2008; Fellow et al., 2012; Downey & Fellow 2013]) are whether there is a non-trivial 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 int(opt) poly(N) time and outputs a solution of size f(opt), forany functions t and f that are independent of N (for Clique, we want f(opt)=(1))? In this paper, we show that both Clique and DomSet admit no non-trivial 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 (e.g., this holds even if f is an exponential or the Ackermann function). 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 (Gap-ETH) [Dinur, 2016, Manurangsi & Raghavendra 2016], which states that no 2^{o(n)}-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - c)-satisfiable for some constant c > 0.Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs. Previously only exact versions of these problems were known to be W[1]-hard [Lin, 2015; Khot & Raman, 2000; Moser & Sikdar, 2009]. Additionally, we rule out k^{o(1)}-FPT-approximation algorithm for Densest k-Subgraph although this ratio does not yet match the trivial O(k)-approximation algorithm.To the best of our knowledge, prior results only rule out constantfactor approximation for Clique [Hajiaghayi et al., 2013; KK13, Bonnet et al., 2015] and log^{1/4+c}(opt) approximation for DomSet for any constant c > 0 [Chen & Lin, 2016]. Our result on Clique significantly improves on [Hajiaghayi et al., 2013; Bonnet et al., 2015]. However, our result on DomSet is incomparable to [Chen & Lin, 2016] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.
Otsikko58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017
ISBN (painettu)978-1-5386-3464-6
DOI - pysyväislinkit
TilaJulkaistu - 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaAnnual Symposium on Foundations of Computer Science
- Berkeley, Yhdysvallat
Kesto: 15 lokak. 201717 lokak. 2017
Konferenssinumero: 58


NimiAnnual Symposium on Foundations of Computer Science
ISSN (painettu)1523-8288
ISSN (elektroninen)2575-8454


ConferenceAnnual Symposium on Foundations of Computer Science


Sukella tutkimusaiheisiin 'From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä