# 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
It is philosophically possible to compose the input graph with a simple error correcting code to amplify this probability to a constant, as we are allowed to blowup the input size by any function of \(k\). In contrast, when \(k\) is not fixed, like in the NP world, \(k\) is of the same magnitude as the input size, and thus we are only allowed to blow up the input size by \(\operatorname{poly}(n)\) factor. Nonetheless, we have to point out that the gadgets typically needed to make the gadget composition technique work must be extremely rich in combinatorial structure (and are typically constructed from random objects or algebraic objects), and were previously studied extensively in the area of extremal combinatorics. Returning to the reduction above from \(k\)-Clique to One-Sided \(k\)-Biclique, it turns out that we do not know how to construct the set system \(\mathcal{T}\), and hence the reduction does not pan out. Nonetheless Lin constructed a variant of \(\mathcal{T}\), where Property 2 was more refined and the reduction from \(k\)-Clique to One-Sided \(k\)-Biclique, went through with slightly more effort. Before we move on to discussing some applications of Theorem 1 and the gadget composition technique, we remark about known stronger time lower bound for One-Sided \(k\)-Biclique under stronger running time hypotheses. Lin [23] showed a lower bound of \(n^{\Omega(\sqrt{k})}\) for One-Sided \(k\)-Biclique assuming ETH. We wonder if this can be further improved. **Open Question 1** (Lower bound of One-Sided \(k\)-Biclique under ETH and SETH). : _Can the running time lower bound on One-Sided \(k\)-Biclique be improved to \(n^{\Omega(k)}\) under ETH? Can it be improved to \(n^{k-o(1)}\) under SETH?_  
We remark that a direction to address the above question was detailed in [24]. While on the topic of the \(k\)-Biclique problem, it is worth noting that the lower bound of \(n^{\Omega(\sqrt{k})}\) for One-Sided \(k\)-Biclique assuming ETH yields a running time lower bound of \(n^{\Omega(\frac{\log k}{\log\log k})}\) for the \(k\)-Biclique problem (due to the soundness parameters in Theorem 1). However, assuming randomized ETH, the running time lower bound for the \(k\)-Biclique problem can be improved to \(n^{\Omega(\sqrt{k})}\)[23]. Can this improved running time lower bound be obtained just under (deterministic) ETH? Finally, we remark that we shall discuss about the hardness of approximation of the \(k\)-Biclique problem in Section 3.2.3. **Inapproximability of \(k\)-Dominating Set via Gadget Composition. ** We shall discuss about the inapproximability of \(k\)-Dominating Set in detail in the next subsubsection. We would like to simply highlight here how the above framework was used by Chen and Lin [25] and Lin [26] to obtain inapproximability results for \(k\)-Dominating Set. In [25], the authors starting from Theorem 1, obtain the W[1]-hardness of approximating \(k\)-Dominating Set to a factor of almost two. Then they amplify the gap to any constant by using a specialized graph product. We now turn our attention to a recent result of Lin [26] who provided strong inapproximability result for \(k\)-Dominating Set (we refer the reader to Section 3.1.2 to obtain the context for this result). Lin's proof of inapproximability of \(k\)-Dominating Set is a one-step reduction from an instance of \(k\)-Set Cover on a universe of size \(O(\log n)\) (where \(n\) is the number of subsets given in the collection) to an instance of \(k\)-Set Cover on a universe of size \(\operatorname{poly}(n)\) with a gap of \(\left(\frac{\log n}{\log\log n}\right)^{1/k}\). Lin then uses this gap-producing self-reduction to provide running time lower bounds (under different time hypotheses) for approximating \(k\)-set cover to a factor of \((1-o(1))\cdot\left(\frac{\log n}{\log\log n}\right)^{1/k}\). Recall that \(k\)-Dominating Set is essentially [27; 28] equivalent to \(k\)-Set Cover.