# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### Hardness from Gap Hypotheses
#### 3.2.3 Inapproximability of \(k\)-Biclique and Densest \(k\)-Subgraph  
While PIH (or equivalently the Multicolored Densest \(k\)-Subgraph problem) can serve as a starting point for hardness of approximation of many problems, there are some problems for which not even a constant factor hardness is known under PIH, but strong inapproximability results can be obtained via Gap-ETH. We will see two examples of this here. First is the \(k\)-Biclique problem. Recall that in this problem, we are given a bipartite graph and we would like to determine whether there is a complete bipartite subgraph of size \(k\). As stated earlier in the previous subsection, despite its close relationship to \(k\)-Clique, \(k\)-Biclique turned out to be a much more challenging problem to prove intractibility and even its W[1]-hardness was only shown recently [23]. This difficulty is corroborated by its approximability status in the classical (non-parameterized) regime; while Clique is long known to be NP-hard to approximate to within \(N^{1-o(1)}\) factor [71], Biclique is not even known to be NP-hard to approximate to within say 1.01 factor [72; 73; 74; 75]. With this in mind, it is perhaps not a surprise that \(k\)-Biclique is not known to be hard to approximate under PIH. Nonetheless, when we assume Gap-ETH, we can in fact prove a very strong hardness of approximation for the problem:  
**Theorem 7** ([39]). : _Assuming Gap-ETH, there is no \(o(k)\)-FPT-approximation for \(k\)-Biclique._  
Note that, similar to \(k\)-Clique, a \(k\)-approximation for Biclique can be easily achieved by outputting a single edge. Hence, in terms of the inapproximability ratio, the above result is tight. Due to its technicality, we only sketch an outline of the proof of Theorem 7 here. Firstly, the reduction starts by constructing a graph that is similar (but not the same) to that of \(k\)-Clique that we describe above. The main properties of this graph is that (i) in the YES case where the formula is satisfiable, the graph contains many copies of \(k\)-Biclique, and (ii) in the NO case where the formula is not even \((1-\delta)\)-satisfiable, the graph contains few copies of \(g\)-Biclique. The construction and these properties were in fact shown in [76]. In [39], it was observed that, if we subsample the graph by keeping each vertex independently with probability \(p\) for an appropriate value of \(p\), then (i) ensuresthat at least one of the \(k\)-Biclique survives the subsampling, whereas (ii) ensures that no \(g\)-Biclique survives. This indeed gives the claimed result in the above theorem. We remark that, while Theorem 7 seems to resolve the approximability of \(k\)-Biclique, there is still one aspect that is not yet completely understood: the running time lower bound. To demonstrate this, recall that, for \(k\)-Clique, the reduction that gives hardness of \(k\)-vs-\(g\)Clique has size \(2^{O(n/\delta)}\); this means that we have a running time lower bound of \(f(k)\cdot N^{\Omega(g)}\) on the problem. This is of course tight, because we can determine whether a graph has a \(g\)-clique in \(N^{O(g)}\) time. However, for \(k\)-Biclique, the known reduction that gives hardness for \(k\)-vs-\(g\)Biclique has size \(2^{O(n/\sqrt{\delta})}\). This results in a running time lower bound of only \(f(k)\cdot N^{\Omega(\sqrt{\delta})}\). Specifically, for the most basic setting of constant factor approximation, Theorem 7 only rules out algorithms with running time \(f(k)\cdot N^{o(\sqrt{\delta})}\). Hence, an immediate question here is:  
**Open Question 8**. : _Is there an \(f(k)\cdot N^{o(k)}\)-time algorithm that approximates \(k\)-Biclique to within a constant factor?_  
To put things into perspective, we note that, even for exact algorithms for \(k\)-Biclique, the best running time lower bound is still \(f(k)\cdot N^{\Omega(\sqrt{k})}\)[23] (under any reasonable complexity assumption).