# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### W[1]-Hardness of Gap Problems
#### 3.1.1 Parameterized Intractability of Biclique and Applications to Parameterized Inapproximability
Elaborating, Lin designs a gadget by combining the hypercube partition gadget of Feige [29] with a derandomizing combinatorial object called universal set, to obtain a gap gadget, and then combines the gap gadget with the input \(k\)-Set Cover instance (on small universe but with no gap) to obtain a gap \(k\)-Set Cover instance. This is another success story of the gadget composition technique. Finally, we remark that Lai [30] recently extended Lin's inapproximability results for dominating set (using the same proof framework) to rule out constant-depth circuits of size \(f(k)n^{o(\sqrt{k})}\) for any computable function \(f\). **Even Set. ** A recent success story of Theorem 1 is its application to resolve a long standing open problem called \(k\)-Minimum Distance Problem (also referred to as \(k\)-Even Set), where we are given as input a generator matrix \(\mathbf{A}\in\mathbb{F}_{2}^{n\times m}\) of a binary linear code and an integer \(k\), and the goal is to determine whether the code has distance at most \(k\). Recall that the distance of a linear code is \(\min\limits_{\bar{0}\
eq\mathbf{x}\in\mathbb{F}_{2}^{m}}\|\mathbf{A}\mathbf{x} \|_{0}\) where \(\|\cdot\|_{0}\) denote the \(0\)-norm (aka the Hamming norm). In [31], the authors showed that \(k\)-Even Set is \(\mathrm{W}[1]\)-hard under randomized reductions. The result was obtained by starting from the inapproximability result stated in Theorem 1 followed by a series of intricate reductions. In fact they proved the following stronger inapproximability result. **Theorem 2** ([31]). : _For any \(\gamma\geq 1\), given input \((\mathbf{A},k)\in\mathbb{F}^{n\times m}\times\mathbb{N}\), it is W[1]-hard (under randomized reductions) to distinguish between_  
* _Completeness: Distance of the code generated by_ \(\mathbf{A}\) _is at most_ \(k\) _, and,_
* _Soundness: Distance of the code generated by_ \(\mathbf{A}\) _is more than_ \(\gamma\cdot k\)We emphasize that even to obtain the W[1]-hardness of \(k\)-Even Set (with no gap), they needed to start from the gap problem given in Theorem 1. The proof of the above theorem proceeds by first showing FPT hardness of approximation of the non-homogeneous variant of \(k\)-Minimum Distance Problem called the \(k\)-Nearest Codeword Problem. In \(k\)-Nearest Codeword Problem, we are given a target vector \(\mathbf{y}\) (in \(\mathbb{F}^{n}\)) in addition to \((\mathbf{A},k)\), and the goal is to find whether there is any \(\mathbf{x}\) (in \(\mathbb{F}^{m}\)) such that the Hamming norm of \(\mathbf{A}\mathbf{x}-\mathbf{y}\) is at most \(k\). As an intermediate step of the proof of Theorem 2, they showed that \(k\)-Nearest Codeword Problem is W[1]-hard to approximate to any constant factor. An important intermediate problem which was studied by [31] to prove the inapproximability of \(k\)-Nearest Codeword Problem, was the \(k\)-Linear Dependent Set problem where given a set \(\mathbf{A}\) of \(n\) vectors over a finite field \(\mathbb{F}_{q}\) and an integer \(k\), the goal is to decide if there are \(k\) vectors in \(\mathbf{A}\) that are linearly dependent. They ruled out constant factor approximation algorithms for this problem running in FPT time. Summarizing, the high level proof overview of Theorem 2 follows by reducing One-Sided \(k\)-Biclique to \(k\)-Linear Dependent Set, which is then reduced to \(k\)-Nearest Codeword Problem, followed by a final randomized reduction to \(k\)-Minimum Distance Problem. Finally, we note that there is no reason to define \(k\)-Minimum Distance Problem only for binary code, but can instead be defined over larger fields as well. It turns out that [31] cannot rule out FPT algorithms for \(k\)-Minimum Distance Problem over \(\mathbb{F}_{p}\) with \(p>2\), when \(p\) is fixed and is not part of the input. Thus we have the open problem. **Open Question 2**.