Parameterized Inapproximability Hypothesis under ETH
Open Access
- 9 October 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 72 (5) , 1-40
Abstract
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ɛ fraction of constraints for some absolute constant ɛ > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under the Gap Exponential Time Hypothesis (ETH), a very strong assumption with an inherent gap. In this work, we prove PIH under the ETH. This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.Keywords
All Related Versions
Funding Information
- NSF (CCF-2228287 and CCF-2211972)
- NSF CAREER (CCF-2145474)
This publication has 55 references indexed in Scilit:
- Partitioning a graph into small pieces with applications to path transversalMathematical Programming, 2018
- Fixed-Parameter and Approximation Algorithms: A New Look2013
- A Constant-Factor Approximation Algorithm for the k-Median ProblemJournal of Computer and System Sciences, 2002
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- Greedy Strikes Back: Improved Facility Location AlgorithmsJournal of Algorithms, 1999
- The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear EquationsJournal of Computer and System Sciences, 1997
- Fixed-parameter tractability and completeness II: On completeness for W[1]Theoretical Computer Science, 1995
- Self-testing/correcting with applications to numerical problemsJournal of Computer and System Sciences, 1993
- A simplified NP-complete satisfiability problemDiscrete Applied Mathematics, 1984