Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
Show others and affiliations
2017 (English)In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE Computer Society, 2017, Vol. 2017, p. 743-754Conference paper, Published paper (Refereed)
Abstract [en]

We consider questions that arise from the intersection between the areas of approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [1], [2], [3]) 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 in t(OPT) poly(N) time and outputs a solution of size f(OPT), for any 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 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) [4], [5], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 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 [6], [7], [8]. 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 constant factor approximation for Clique [9], [10] and log(1/4+epsilon) (OPT) approximation for DomSet for any constant epsilon > 0 [11]. Our result on Clique significantly improves on [9], [10]. However, our result on DomSet is incomparable to [11] since their results hold under ETH while our results hold under Gap-ETH, which is a stronger assumption.

Place, publisher, year, edition, pages
IEEE Computer Society, 2017. Vol. 2017, p. 743-754
Series
Annual IEEE Symposium on Foundations of Computer Science, ISSN 0272-5428
Keywords [en]
Fixed Parameter Tractability, Hardness of Approximation, Clique, Set Cover, Dominating Set
National Category
Discrete Mathematics Signal Processing
Identifiers
URN: urn:nbn:se:kth:diva-220660DOI: 10.1109/FOCS.2017.74ISI: 000417425300065Scopus ID: 2-s2.0-85041136063ISBN: 978-1-5386-3464-6 OAI: oai:DiVA.org:kth-220660DiVA, id: diva2:1172101
Conference
58th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2017, DoubleTree Hotel at the Berkeley Marina, Berkeley, United States, 15 October 2017 through 17 October 2017
Note

QC 20180109

Available from: 2018-01-09 Created: 2018-01-09 Last updated: 2018-02-06Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Na Nongkai, Danupon

Search in DiVA

By author/editor
Na Nongkai, Danupon
By organisation
Theoretical Computer Science, TCS
Discrete MathematicsSignal Processing

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 8 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf