# 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  
In this subsubsection, we will discuss the parametrized inapproximability of the one-sided biclique problem, and show how both that result and its proof technique lead to more inapproximability results. We begin our discussion by formally stating the \(k\)-Biclique problem where we are given as input a graph \(G\) and an integer \(k\), and the goal is to determine whether \(G\) contains a complete bipartite subgraph with \(k\) vertices on each side. The complexity of \(k\)-Biclique was a long standing open problem and was resolved only recently by Lin [23] where he showed that it is \(\mathrm{W}[1]\)-hard. In fact, he showed a much stronger result and this shall be the focus of attention in this subsubsection. **Theorem 1** ([23]). : _Given a bipartite graph \(G(L\dot{\cup}R,E)\) and \(k\in\mathbb{N}\) as input, it is W[1]-hard to distinguish between the following two cases:_  
* _Completeness: There are_ \(k\) _vertices in_ \(L\) _with at least_ \(n^{\Theta(\frac{1}{k})}\) _common neighbors in_ \(R\)_;_
* _Soundness: Any_ \(k\) _vertices in_ \(L\) _have at most_ \((k+6)!\) _common neighbors in_ \(R\)_._  
We shall refer to the gap problem in the above theorem as the One-Sided \(k\)-Biclique problem. To prove the above result, Lin introduced a technique which we shall refer to as Gadget Composition. The gadget composition technique has found more applications since [23]. We provide below a failed approach (given in [23]) to prove the above theorem; nonetheless it gives us good insight into how the gadget composition technique works. Suppose we can construct a set family \(\mathcal{T}=\{S_{1},S_{2},\ldots,S_{n}\}\) of subsets of \([n]\) for some integers \(k\), \(n\) and \(h>\ell\) (for example, \(h=n^{1/k}\) and \(\ell=(k+1)!\)) such that:  
Property 1: Any \(k+1\) distinct subsets in \(\mathcal{T}\) have intersection size at most \(\ell\);  
Property 2: Any \(k\) distinct subsets in \(\mathcal{T}\) have intersection size at least \(h\). Then we can combine \(\mathcal{T}\) with an instance of \(k\)-Clique to obtain a gap instance of One-Sided \(k\)-Biclique as follows. Given a graph \(G\) and parameter \(k\) with \(V(G)\subseteq[n]\), we construct our instance of One-Sided \(k\)-Biclique, say \(H(L\dot{\cup}R,E(H))\) by setting \(L:=E(G)\) and \(R:=[n]\), where for any \((v_{i},v_{j})\in L\) and \(v\in[n]\), we have that \(((v_{i},v_{j}),v)\in E(H)\) if and only if \(v\in S_{i}\cap S_{j}\). Let \(s:=k(k-1)/2\). It is easy to check that if \(G\) has a \(k\)-vertex clique, say \(\{v_{1}^{*},\ldots,v_{k}^{*}\}\) is a clique in \(G\), then Property 2 implies that \(|\Delta:=\bigcap_{i\in[k]}S_{v_{i}^{*}}|\geq h\). It follows that the set of \(s\) vertices in \(L\) given by \(\{(v_{i}^{*},v_{j}^{*}):\) for all \(\{i,j\}\in(\frac{|k|}{2})\}\) are neighbors of every vertex in \(\Delta\subseteq R\). On the other hand, if \(G\) contains no \(k\)-vertex clique, then any \(s\) distinct vertices in \(L\) (i.e., \(s\) edges in \(G\)) must have at least \(k+1\) vertices in \(G\) as their end points. Say \(V^{\prime}\) was the set of all vertices contained the \(s\) edges. By Property 1, we know that \(|\Delta^{\prime}:=\bigcap_{v\in V^{\prime}}S_{v}|\leq\ell\), and thus any \(s\) distinct vertices in \(L\) have at most \(\ell\) common neighbors in \(R\). It is indeed very surprising that this technique can yield non-trivial inapproximability results, as the gap is essentially produced from the gadget and is oblivious to the input! This also stands in stark contrast to the PCP theorem and hardness of approximation results in NP, where all known results were obtained by global transformations on the input. The key difference between the parameterized and NP worlds is the notion of locality. For example, consider the \(k\)-Clique problem, if a graph does not have a clique of size \(k\), then given any \(k\) vertices, a random vertex pair in these \(k\) vertices does not have an edge with probability at least \(1/k^{2}\).