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:
- 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.
- 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.
- 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.
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.
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