# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 3 FPT Hardness of Approximation
### W[1]-Hardness of Gap Problems
#### 3.1.2 Parameterized Inapproximability of Dominating Set
We further define  
\[\alpha:=1-\frac{1}{\left(\binom{k}{2}\cdot F(\binom{k}{2})\right)^{\binom{k}{2}}}.\]  
From \(k\)-Multicolor Clique to \(k\)-Cap CSP.Starting from an instance of \(k\)-Multicolor Clique, say \(G\) on vertex set \(V:=V_{1}\dot{\cup}V_{2}\dot{\cup}\cdots\dot{\cup}V_{k}\), we write down a set of constraints \(\mathcal{P}\) on a variable set \(X:=\{x_{i,j}\mid i,j\in[k],i\
eq j\}\) as follows. For every \(i,j\in[k]\), such that \(i\
eq j\), define \(E_{i,j}\) to be the set of all edges in \(G\) whose end points are in \(V_{i}\) and \(V_{j}\). An assignment to variable \(x_{i,j}\) is an element of \(E_{i,j}\), i.e., a pair of vertices, one from \(V_{i}\) and the other from \(V_{j}\). Suppose that \(x_{i,j}\) was assigned the edge \(\{v_{i},v_{j}\}\), where \(v_{i}\in V_{i}\) and \(v_{j}\in V_{j}\). Then we define the assignment of \(x^{i}_{i,j}\) to be \(v_{i}\) and the assignment of \(x^{i}_{i,j}\) to be \(v_{j}\). We define \(\mathcal{P}:=\{P_{1},\ldots,P_{k}\}\), where the constraint \(P_{i}\) is defined to be satisfied if the assignment to all of \(x^{i}_{1,i^{\prime}},x^{i}_{2,i^{\prime}},\ldots,x^{i}_{i-1,i^{\prime}},x^{i}_{ k,i^{\prime}}\) are the same. We refer to the problem of determining if there is an assignment to the variables in \(X\) such that all the constraints are satisfied as the \(k\)-CSP problem. Notice that while this is a natural way to write \(k\)-Multicolor Clique as a CSP, where we have tried to check if all variables having a vertex in common, agree on its assignment, there is no gap yet in the \(k\)-CSP problem. In particular, if there was a clique of size \(k\) in \(G\) then there is an assignment to the variables of \(X\) (by assigning the edges of the clique in \(G\) to the corresponding variable in \(X\)) such that all the constraints in \(\mathcal{P}\) are satisfied; however, if every clique in \(G\) is of size less than \(k\) then there every assignment to the variables of \(X\) may violate only one constraint in \(\mathcal{P}\) (and not more). In order to amplify the gap, we rewrite the set of constraints \(\mathcal{P}\) in a different way to obtain the set of constraints \(\mathcal{P}^{\prime}\), on the same variable set \(X\), as follows. Suppose that \(x_{i,j}\) was assigned the edge \(\{v_{i},v_{j}\}\), where \(v_{i}\in V_{i}\) and \(v_{j}\in V_{j}\), then for \(\beta\in[\log n]\), we define the assignment of \(x^{i,\beta}_{i,j}\) to be the \(\beta^{\text{th}}\) coordinate of \(v_{i}\). Recall that \(|V_{i}|=n\) and therefore we can label all vertices in \(V_{i}\) by vectors in \(\{0,1\}^{\log n}\). We define \(\mathcal{P}^{\prime}:=\{P^{\prime}_{1},\ldots,P^{\prime}_{\log n}\}\), where the constraint \(P^{\prime}_{\beta}\) is defined to be satisfied if and only if the following holds for all \(i\in[k]\): the assignment to all of \(x^{i,\beta}_{11},x^{i,\beta}_{2,i^{\prime}},\ldots,x^{i,\beta}_{i-1,i^{\prime }},x^{i,\beta}_{i+1,i^{\prime}},\ldots,x^{i,\beta}_{k,i}\) are the same. Again notice that there is an assignment to the variables of \(X\) such that all the constraints in \(\mathcal{P}\) are satisfied if and only if the same assignment also satisfies all the constraints in \(\mathcal{P}^{\prime}\). However, rewriting \(\mathcal{P}\) as \(\mathcal{P}^{\prime}\) allows us to simply apply the error correcting code \(C_{\ell}\) (with parameters \(\rho\) and \(\delta\), and encoding function \(\mathcal{E}_{C_{\ell}}\)) to the constraints in \(\mathcal{P}^{\prime}\), to obtain a gap! In particular, we choose \(\ell\) to be such that \(\rho\ell=\log n\). Consider a new set of constraints \(\mathcal{P}^{\prime\prime}\), on the same variable set \(X\), as follows. For any \(z\in\{0,1\}^{\log n}\) and \(\beta\in[\ell]\), we denote by \(\mathcal{E}_{C_{\ell}}(z)_{\beta}\), the \(\beta^{\text{th}}\) coordinate of \(\mathcal{E}_{C_{\ell}}(z)\).