# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### Hardness from Gap Hypotheses
#### 3.2.2 Strong Inapproximability of Multicolored Densest \(k\)-Subgraph and Label Cover  
For our second example, we go back to the Multicolored Densest \(k\)-Subgraph once again. Recall that PH asserts that this problem is hard to approximate to some constant factor, and we have seen above that Gap-ETH also implies this. On the approximation front, however, only the trivial \(k\)-approximation algorithm is known: just pick a vertex that has edges to as many partitions as possible. Then, output that vertex and one of its neighbors from each partition. It is hence a natural question to ask whether it is possible to beat this approximation ratio. This question has been, up to lower order terms, answered in the negative, assuming Gap-ETH:  
**Theorem 6** ([59]). : _Assuming Gap-ETH, there is no \(k^{1-o(1)}\)-approximation for Multicolored Densest \(k\)-Subgraph._  
An interesting aspect of the above result is that, even in the NP-hardness regime, no NP-hardness of factor \(k^{\gamma}\) for some constant \(\gamma>0\) is known. In fact, the problem is closely related to (and is a special case of) a well-known conjecture in the hardness of approximation community called the Sliding Scale Conjecture (SSC) [60; 61; 62]. (See [59] for more discussion on the relation between the two.) Thus, this is yet another instance where taking a parameterized complexity perspective helps us advance knowledge even in the classical settings. To prove Theorem 6, arguably the most natural reduction here is the above reduction for Cliquel Note that we now view the vertices corresponding to each subset \(C_{i}\) as forming a partition \(V_{i}\). The argument in the YES case is exactly the same as before: if the formula is satisfiable, then there is a (multicolored) \(k\)-clique. However, as the readers might have noticed, the argument in the NO case does not go through anymore. In particular, even when the graph is quite dense (e.g., having half of the edges present), it may not contain any large clique at all and hence it is unclear how to recover back an assignment that satisfies a large fraction of constraints. This obstacle was overcomed in [59] by proving an agreement testing theorem (i.e., direct product theorem), which is of the following form. Given \(k\) local functions \(f_{1},\ldots,f_{k}\), where \(f_{i}:S_{i}\to\{0,1\}\) is a boolean function whose domain \(S_{i}\) is a subset of a universe \(\mathcal{U}\). If some (small) \(\zeta\) fraction of the pairs agree [63] with each other, then we can find (i.e., \"decode\") a global function \(h:[n]\to\{0,1\}\) that \"approximately agrees\" with roughly \(\zeta\) fraction of the local functions. The theorem in [59] works when \(S_{1},\ldots,S_{k}\) are sets of size \(\Omega(n)\). Due to the technical nature of the definitions, we will not fully formalize the notions in the previous paragraph. Nonetheless, let us sketch how to apply the agreement testing theorem to prove the NO case for our reduction. Suppose for the sake of contradiction that the formula is not \((1-\delta)\)-satisfiable and that there exists a \(k\)-subgraph with density \(\zeta\geq\frac{1}{k^{1-o(1)}}\). Recall that each selected vertex is simply a partial assignment onto the subset of clauses \(C_{i}\) for some \(i\); we may view this as a function \(f_{i}:S_{i}\to\{0,1\}\) where \(S_{i}\) denote the set of variables that appear in \(C_{i}\). Here the universe \(\mathcal{U}\) is the set of all variables. With this perspective, we can apply the agreement testing theorem to recover a global function \(h:\mathcal{U}\to\{0,1\}\) that \"approximately agrees\" with roughly \(\zeta k\) of the local functions. Notice that, in this context, \(h\) is simply a global assignment for the CNF formula. Previously in the proof for inapproximability of Clique, we had a global assignment that (perfectly) agrees with \(g\) local functions, from which we can conclude that this assignment satisfies all but \(\delta\) fraction of the clauses.