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

Introduction

The intersection of approximation algorithms and parameterized complexity has long sought to answer a fundamental question: can we solve hard problems more efficiently if we settle for an approximate solution? This paper provides a definitive "no" for several cornerstone problems in computer science. By leveraging the Gap Exponential Time Hypothesis (Gap-ETH), the authors demonstrate that for problems like Maximum Clique and Minimum Dominating Set, finding even a very loose approximation is as hard as finding the exact solution.

The FPT-Approximation Challenge

In the realm of Fixed-Parameter Tractability (FPT), we aim to solve problems in time $f(k) \cdot poly(N)$, where $k$ is a parameter (often the size of the optimal solution, OPT) and $N$ is the input size. While many NP-hard problems are FPT, others like Clique and Dominating Set are believed to be hard even in this setting (specifically, they are $W[1]$-hard).

The "holy grail" of this field has been to determine if these problems admit non-trivial FPT-approximations. For instance, if the maximum clique size is $k$, can we find a clique of size $k/2$ or $\sqrt{k}$ in FPT time? Previous research could only rule out constant-factor approximations for Clique or specific logarithmic factors for Dominating Set. This paper aims for "total" inapproximability—proving that no meaningful approximation exists in FPT time for these problems.

Methodology: Gap-ETH and Vertex Compression

The core of the authors' approach is the Gap Exponential Time Hypothesis (Gap-ETH). Unlike the standard ETH, which posits that 3SAT cannot be solved in subexponential time, Gap-ETH asserts that it is hard to even distinguish between a fully satisfiable 3SAT formula and one where no assignment satisfies more than a $(1-\epsilon)$ fraction of clauses.

To translate this gap into the FPT regime, the authors introduced several key innovations:

  1. Inherently Enumerative Concept: They formalize the idea that some problems are "inherently enumerative," meaning the most efficient way to find a solution of size $r$ is to check all $N^r$ possibilities, regardless of how much larger the actual optimum might be.
  2. Label Cover with Vertex Compression: By applying a compression technique to the standard Label Cover reduction—randomly sub-sampling or grouping vertices—they successfully mapped the hardness of Label Cover onto the "small OPT" regime characteristic of FPT problems.
  3. Gap Amplification: For maximization problems like Clique, randomized graph products were used to amplify the gap between "large" and "small" instances, further strengthening the lower bounds.

Key Results

The paper establishes unprecedented lower bounds under the Gap-ETH assumption. For Maximum Clique, the authors prove there is no $o(OPT)$-FPT-approximation, meaning one cannot find a clique of any size that grows significantly with the optimum faster than brute force.

Table 1: FPT-inapproximability lower bounds for Maximum Clique and related maximization problems.

For Minimum Dominating Set, the result is even more striking: there is no $f(OPT)$-FPT-approximation for any computable function $f$. This represents a "total" hardness result, showing that the gap between the optimal and an approximate solution does not reduce the parameterized complexity of the problem.

Table 2: FPT-inapproximability lower bounds for Minimum Dominating Set and related minimization problems.

Beyond these two, the authors extended their results to:

  • Maximum Biclique and Induced Matching: Ruling out non-trivial FPT-approximations.
  • Densest $k$-Subgraph: Improving the lower bound to $k^{o(1)}$, narrowing the gap toward the trivial $O(k)$ upper bound.
  • Maximum Induced Subgraphs: Proving hardness for properties like planarity.

Conclusion and Future Work

This work fundamentally changes our understanding of FPT-approximability, suggesting that for many $W[1]$-hard problems, approximation is not a viable path to tractability. While these results rely on the strong Gap-ETH assumption, they provide a robust framework for proving lower bounds. Future research may focus on recovering these results under weaker assumptions like standard ETH or $W[1] \neq FPT$, and further closing the gap for problems like Densest $k$-Subgraph.

Summary updated

Abstract

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) = ω(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 (GapETH) [4], [5], which states that no 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(n)</sup> -time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even (1 - ε)-satisfiable for some constant ε > 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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(1)</sup> -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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/4+ε</sup> (OPT) approximation for DomSet for any constant ε > 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.
BibTeX
@inproceedings{chalermsook2017from,
  author = {Parinya Chalermsook and Marek Cygan and Guy Kortsarz and Bundit Laekhanukit and Pasin Manurangsi and Danupon Nanongkai and Luca Trevisan},
  title = {{From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More}},
  booktitle = {FOCS},
  year = {2017},
  url = {https://openreview.net/forum?id=LvZaLSuP-mW},
}
Figure