# 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
: _Is it W[1]-hard to decide \(k\)-Minimum Distance Problem over \(\mathbb{F}_{p}\) with \(p>2\), when \(p\) is fixed and is not part on the input?_  
Shortest Vector Problem.Theorem 1 (or more precisely the constant inapproximability of \(k\)-Linear Dependent Set stated above) was also used to resolve the complexity of the parameterized \(k\)-Shortest Vector Problem in lattices, where the input (in the \(\ell_{p}\) norm) is an integer \(k\in\mathbb{N}\) and a matrix \(\mathbf{A}\in\mathbb{Z}^{n\times m}\) representing the basis of a lattice, and we want to determine whether the shortest (non-zero) vector in the lattice has length at most \(k\), i.e., whether \(\min\limits_{\bar{\partial}\
eq\mathbf{x}\in\mathbb{Z}^{m}}\|\mathbf{A}\mathbf{ x}\|_{p}\leq k\). Again, \(k\) is the parameter of the problem. It should also be noted here that (as in [32]), we require the basis of the lattice to be integer valued, which is sometimes not enforced in literature (e.g., [33; 34]). This is because, if \(\mathbf{A}\) is allowed to be any matrix in \(\mathbb{R}^{n\times m}\), then parameterization is meaningless because we can simply scale \(\mathbf{A}\) down by a large multiplicative factor. In [31], the authors showed that \(k\)-Shortest Vector Problem is W[1]-hard under randomized reductions. In fact they proved the following stronger inapproximability result. **Theorem 3** ([31]). : _For any \(p>1\), there exists a constant \(\gamma_{p}>1\) such that given input \((\mathbf{A},k)\in\mathbb{Z}^{n\times m}\times\mathbb{N}\), it is W[1]-hard (under randomized reductions) to distinguish between_  
* _Completeness: The_ \(\ell_{p}\) _norm of the shortest vector of the lattice generated by_ \(\mathbf{A}\) _is_ \(\leq k\)_, and,_
* _Soundness: The_ \(\ell_{p}\) _norm of the shortest vector of the lattice generated by_ \(\mathbf{A}\) _is_ \(>\gamma_{p}\cdot k\)_._  
Notice that Theorem 2 rules out FPT approximation algorithms with any constant approximation ratio for \(k\)-Even Set. In contrast, the above result only prove FPT inapproximability with some constant ratio for \(k\)-Shortest Vector Problem in \(\ell_{p}\) norm for \(p>1\). As with \(k\)-Even Set, even to prove the W[1]-hardness of \(k\)-Shortest Vector Problem (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\)-Shortest Vector Problem called the \(k\)-Nearest Vector Problem. In \(k\)-Nearest Vector Problem, we are given a target vector \(\mathbf{y}\) (in \(\mathbb{Z}^{n}\)) in addition to \((\mathbf{A},k)\), and the goal is to find whether there is any \(\mathbf{x}\) (in \(\mathbb{Z}^{m}\)) such that the \(\ell_{p}\) 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 Vector Problem is W[1]-hard to approximate to any constant factor. Summarizing, the high level proof overview of Theorem 3 follows by reducing One-Sided \(k\)-Biclique to \(k\)-Linear Dependent Set, which is then reduced to \(k\)-Nearest Vector Problem, followed by a final randomized reduction to \(k\)-Shortest Vector Problem. An immediate open question left open from their work is whether Theorem 3 can be extended to \(k\)-Shortest Vector Problem in the \(\ell_{1}\) norm. In other words,  
**Open Question 3** (Approximation of \(k\)-Shortest Vector Problem in \(\ell_{1}\) norm). : _Is \(k\)-Shortest Vector Problem in the \(\ell_{1}\) norm in FPT?_