We present a simple deterministic reduction which, assuming the Exponential Time Hypothesis (ETH), yields tight lower bounds for approximating the parameterized Maximum Likelihood Decoding problem (MLD) and the parameterized Nearest Codeword Problem (NCP) within some fixed constant factor. Our starting point is the ETH-based exponential-time hardness of (c, s)-Gap MAXLIN established in [Nir Bitansky et al., 2024]. We transform a (c, s)-Gap MAXLIN instance into an instance of γ-Gap k-MLD via a novel combinatorial object that we call a cover family. We provide both a randomized construction of the required cover families and a subsequent derandomization. Prior to our work, n^{Ω(k)} hardness for constant-factor approximation was only shown under the randomized Gap Exponential Time Hypothesis Gap-ETH [Pasin Manurangsi, 2020], which is a much stronger assumption than ETH. Under ETH, the strongest known lower bound was n^{Ω(k/poly log k)} due to [Mitali Bafna et al., 2025]. Unlike previous approaches that rely on reductions from the hardness of approximating 2-CSP, our reduction provides a more direct and conceptually simpler route to achieving the optimal lower bounds.

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ϵ> 0 such that for any computable function f:λ.,•→λ.,•, no f(k)· nO(1)-time algorithm can, on input a k-variable CSP instance with domain size n, find an assignment satisfying 1-ϵ fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC'24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires nk1-o(1) time. This immediately implies, for example, that finding a (k/2)-clique in an n-vertex graph with a k-clique requires nk1-o(1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k-ExactCover and Max k-Coverage. Our proof follows the blueprint of the previous work to identify a "vector-structured"ETH-hard CSP whose satisfiability can be checked via an appropriate form of "parallel"PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing.

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.

In this paper we present a new gap-creating randomized self-reduction for parameterized Maximum Likelihood Decoding problem over $\mathbb{F}_p$ ($k$-MLD$_p$). The reduction takes a $k$-MLD$_p$ instance with $k\cdot n$ vectors as input, runs in time $f(k)n^{O(1)}$ for some computable function $f$, outputs a $(3/2-\varepsilon)$-Gap-$k'$-MLD$_p$ instance for any $\varepsilon>0$, where $k'=O(k^2\log k)$. Using this reduction, we show that assuming the randomized Exponential Time Hypothesis (ETH), no algorithms can approximate $k$-MLD$_p$ (and therefore its dual problem $k$-NCP$_p$) within factor $(3/2-\varepsilon)$ in $f(k)\cdot n^{o(\sqrt{k/\log k})}$ time for any $\varepsilon>0$. We then use reduction by Bhattacharyya, Ghoshal, Karthik and Manurangsi (ICALP 2018) to amplify the $(3/2-\varepsilon)$-gap to any constant. As a result, we show that assuming ETH, no algorithms can approximate $k$-NCP$_p$ and $k$-MDP$_p$ within $γ$-factor in $f(k)n^{o(k^{\varepsilon_γ})}$ time for some constant $\varepsilon_γ>0$. Combining with the gap-preserving reduction by Bennett, Cheraghchi, Guruswami and Ribeiro (STOC 2023), we also obtain similar lower bounds for $k$-MDP$_p$, $k$-CVP$_p$ and $k$-SVP$_p$. These results improve upon the previous $f(k)n^{Ω(\mathsf{poly} \log k)}$ lower bounds for these problems under ETH using reductions by Bhattacharyya et al. (J.ACM 2021) and Bennett et al. (STOC 2023).

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 Gap-ETH, a very strong assumption with an inherent gap. In this work, we prove PIH under the Exponential Time Hypothesis (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.

In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no $f(k) \cdot n^{k^{o(1 / \log \log k)}}$-time algorithm that can decide whether an n-vertex graph contains a clique of size k or contains no clique of size $k / 2$, and no FPT algorithm can decide whether an input graph has a clique of size k or no clique of size $k / f(k)$, where $f(k)$ is some function in $k^{1-o(1)}$. Our results significantly improve the previous works [1], [2]. The crux of our proof is a framework to construct gap-producing reductions for the k-CLIQUE problem. More precisely, we show that given an error-correcting code $C: \Sigma_{1}^{k} \rightarrow \Sigma_{2}^{k^{\prime}}$ that is locally testable and smooth locally decodable in the parallel setting, one can construct a reduction which on input a graph G outputs a graph $G^{\prime}$ in $\left(k^{\prime}\right)^{O(1)} \cdot n^{O\left(\log \left|\Sigma_{2}\right| / \log \left|\Sigma_{1}\right|\right)}$ time such•if G has a clique of size k, then $G^{\prime}$ has a clique of size K, where $K=\left(k^{\prime}\right)^{O(1)}$.•if G has no clique of size k, then $G^{\prime}$ has no clique of size $(1-\varepsilon) \cdot K$ for some constant $\varepsilon \in(0,1)$.We then construct such a code with $k^{\prime}=k^{\Theta(\log \log k)}$ and $\left|\Sigma_{2}\right|=\left|\Sigma_{1}\right|^{k^{0.54}}$, establishing the hardness result above. Our code generalizes the derivative code [3] into the case with a super constant order of derivatives.

Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are problems which remain hard on graphs of bounded treewidth. In this paper, we consider three vertex selection problems that are W[1]-hard when parameterized by the treewidth of the input graph, namely the capacitated vertex cover problem, the target set selection problem and the vector dominating set problem. We provide two new methods to obtain FPT approximation algorithms for these problems. For the capacitated vertex cover problem and the vector dominating set problem, we obtain $(1+o(1))$-approximation FPT algorithms. For the target set selection problem, we give an FPT algorithm providing a tradeoff between its running time and the approximation ratio.

In this paper, we prove that it is W[2]-hard to approximate k-SETCOVER within any constant ratio. Our proof is built upon the recently developed threshold graph composition technique. We propose a strong notion of threshold graphs and use a new composition method to prove this result. Our technique could also be applied to rule out polynomial time ratio approximation algorithms for the non-parameterized k-SETCOVER problem with k as small as , assuming W[1] ≠ FPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects.

Given a simple graph $G$ and an integer $k$, the goal of $k$-Clique problem is to decide if $G$ contains a complete subgraph of size $k$. We say an algorithm approximates $k$-Clique within a factor $g(k)$ if it can find a clique of size at least $k / g(k)$ when $G$ is guaranteed to have a $k$-clique. Recently, it was shown that approximating $k$-Clique within a constant factor is W[1]-hard [Lin21]. We study the approximation of $k$-Clique under the Exponential Time Hypothesis (ETH). The reduction of [Lin21] already implies an $n^{Ω(\sqrt[6]{\log k})}$-time lower bound under ETH. We improve this lower bound to $n^{Ω(\log k)}$. Using the gap-amplification technique by expander graphs, we also prove that there is no $k^{o(1)}$ factor FPT-approximation algorithm for $k$-Clique under ETH. We also suggest a new way to prove the Parameterized Inapproximability Hypothesis (PIH) under ETH. We show that if there is no $n^{O(\frac{k}{\log k})}$ algorithm to approximate $k$-Clique within a constant factor, then PIH is true.

For every graph G, let ω(G) be the largest size of complete subgraph in G. This paper presents a simple algorithm which, on input a graph G, a positive integer k and a small constant є>0, outputs a graph G′ and an integer k′ in 2Θ(k5)· |G|O(1)-time such that (1) k′≤ 2Θ(k5), (2) if ω(G)≥ k, then ω(G′)≥ k′, (3) if ω(G)<k, then ω(G′)< (1−є)k′. This implies that no f(k)· |G|O(1)-time algorithm can distinguish between the cases ω(G)≥ k and ω(G)

The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix and an integer , determine whether the code generated by has distance at most , or, in other words, whether there is a nonzero vector such that has at most nonzero coordinates. The question of whether -Even Set is fixed parameter tractable (FPT) parameterized by the distance has been repeatedly raised in the literature; in fact, it is one of the few remaining open questions from the seminal book of Downey and Fellows [1999]. In this work, we show that -Even Set is W [1]-hard under randomized reductions. We also consider the parameterized -Shortest Vector Problem (SVP) , in which we are given a lattice whose basis vectors are integral and an integer , and the goal is to determine whether the norm of the shortest vector (in the norm for some fixed ) is at most . Similar to -Even Set, understanding the complexity of this problem is also a long-standing open question in the field of Parameterized Complexity. We show that, for any , -SVP is W [1]-hard to approximate (under randomized reductions) to some constant factor.

Given an edged-weighted graph G, the min-k-cut problem asks for a set of edges with minimum total weight whose removal breaks the graph G into at least k connected components. It is well-known that the greedy algorithm can find a (2 – 2/k)-approximation of the min-k-cut in polynomial time. Assuming the Small Set Expansion Hypothesis (SSEH), no polynomial time algorithm can achieve an approximation ratio better than two [9]. Recently, Gupta, Lee and Li [5] gave a 1.9997-approximation FPT algorithm for the min-k-cut parameterized by k. They also improved this approximation ratio to 1.81 [4]. We generalize their proof techniques and show that the min-k-cut has a nearly 5/3-approximation FPT algorithm. Our proof is self-contained and much shorter than that of Gupta, Lee and Li.

Given an $n$-vertex bipartite graph $I=(S,U,E)$, the goal of set cover problem is to find a minimum sized subset of $S$ such that every vertex in $U$ is adjacent to some vertex of this subset. It is NP-hard to approximate set cover to within a $(1-o(1))\ln n$ factor. If we use the size of the optimum solution $k$ as the parameter, then it can be solved in $n^{k+o(1)}$ time. A natural question is: can we approximate set cover to within an $o(\ln n)$ factor in $n^{k-ε}$ time? In a recent breakthrough result, Karthik, Laekhanukit and Manurangsi showed that assuming the Strong Exponential Time Hypothesis (SETH), for any computable function $f$, no $f(k)\cdot n^{k-ε}$-time algorithm can approximate set cover to a factor below $(\log n)^{\frac{1}{poly(k,e(ε))}}$ for some function $e$. This paper presents a simple gap-producing reduction which, given a set cover instance $I=(S,U,E)$ and two integers $k

A set $D$ of vertices of a graph $G$ is a dominating set if every vertex of $G$ is contained in $D$ or adjacent to some vertex of $D$. The number of vertices in a smallest dominating set of $G$ is denoted by $\gamma(G)$. We prove that, under the assumption ${FPT}\ne {W}[1]$ from parameterized complexity, for any constant $c\in \mathbb{N}^+$ and computable function $f: \mathbb{N}\to \mathbb{N}$ there is no algorithm which on every input graph $G$ finds a dominating set of size at most $c\cdot \gamma(G)$ in $f(\gamma(G))\cdot |G|^{O(1)}$ time. In other words, any constant approximation of the parameterized dominating set problem is ${W}[1]$-hard. Furthermore, assuming the exponential time hypothesis (ETH) [R. Impagliazzo and R. Paturi, J. Comput. System Sci., 62 (2001), pp. 367--375], we can even rule out the existence of a $f(\gamma(G))\cdot |G|^{{({log}\;\gamma(G))}^{{\varepsilon}/{12}}}$-time algorithm which on every input graph $G$ outputs a dominating set of size at most $\sqrt[3+\varepsilon]{{log}\; (\gamma(G))} \cdot \gamma(G)$ for every $0<\varepsilon<1$. Our hardness reduction is built on the second author's recent ${W}[1]$-hardness proof of the biclique problem [B. Lin, The parameterized complexity of $k$-Biclique, in Proceedings of the 26th Annual ACM--SIAM Symposium on Discrete Algorithms, SODA 2015 (San Diego, CA), ACM, New York, SIAM, Philadelphia, 2015, pp. 605--615]. This yields, among other things, a proof without the probabilistically checkable proof (PCP) machinery that the classic dominating set problem has no polynomial time constant approximation under ETH.

Given a graph G and an integer k , the k -B iclique problem asks whether G contains a complete bipartite subgraph with k vertices on each side. Whether there is an f ( k ) ċ | G | O (1) -time algorithm, solving k -B iclique for some computable function f has been a longstanding open problem. We show that k -B iclique is W[1] -hard, which implies that such an f ( k ) ċ | G | O (1) -time algorithm does not exist under the hypothesis W[1] ≠ FPT from parameterized complexity theory. To prove this result, we give a reduction which, for every n -vertex graph G and small integer k , constructs a bipartite graph H = ( L ⊍ R , E ) in time polynomial in n such that if G contains a clique with k vertices, then there are k ( k − 1)/2 vertices in L with n θ(1/ k ) common neighbors; otherwise, any k ( k − 1)/2 vertices in L have at most ( k +1)! common neighbors. An additional feature of this reduction is that it creates a gap on the right side of the biclique. Such a gap might have further applications in proving hardness of approximation results. Assuming a randomized version of Exponential Time Hypothesis, we establish an f ( k ) ċ | G | o (√ k ) -time lower bound for k - Biclique for any computable function f . Combining our result with the work of Bulatov and Marx [2014], we obtain a dichotomy classification of the parameterized complexity of cardinality constraint satisfaction problems.

We prove that there is no fpt-algorithm that can approximate the dominating set problem with any constant ratio, unless FPT = W[1]. Our hardness reduction is built on the second author's recent W[1]-hardness proof of the biclique problem [25]. This yields, among other things, a proof without the PCP machinery that the classical dominating set problem has no polynomial time constant approximation under the exponential time hypothesis.

Given a graph G and a parameter k, the k-Blclique problem asks whether G contains a complete bipartite subgraph Kk,k. This is one of the most easily stated problems on graphs whose parameterized complexity has been long unknown. We prove that k-Blclique is W[1]-hard by giving an fpt-reduction from k-Clique to k-Blclique, thus solving this longstanding open problem.