# 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 define \(\mathcal{P}^{\prime\prime}:=\{P^{\prime\prime}_{1},\ldots,P^{\prime\prime}_{ \ell}\}\), where the constraint \(P^{\prime\prime}_{\beta}\) is defined to be satisfied if and only if the following holds for all \(i\in[k]\): the assignment to all of \(\mathcal{E}_{C_{\ell}}(x^{i}_{1,i})_{\beta},\mathcal{E}_{C_{\ell}}(x^{i}_{2,i })_{\beta},\ldots,\mathcal{E}_{C_{\ell}}(x^{i}_{1-1,i})_{\beta},\mathcal{E}_{C _{\ell}}(x^{i}_{i+1,i})_{\beta},\ldots,\mathcal{E}_{C_{\ell}}(x^{i}_{k,i})_{\beta}\) are the same. Notice, as before, that there is an assignment to the variables of \(X\) such that all the constraints in \(\mathcal{P}^{\prime}\) are satisfied if and only if the same assignment also satisfies all the constraints in \(\mathcal{P}^{\prime\prime}\). However, for every assignment to \(X\) that violates at least one constraint in \(\mathcal{P}^{\prime}\), we have that the same assignment violates at least \(\delta\) fraction of the constraints in \(\mathcal{P}^{\prime\prime}\). To see this, consider an assignment that violates the constraint \(P_{1}\) in \(\mathcal{P}^{\prime\prime}\). This implies that there is some \(i\in[k]\) such that the assignment to all of \(x^{i,1}_{1,i},x^{i,1}_{2,i},\ldots,x^{i,1}_{i-1,i},x^{i,1}_{i+1,i},\ldots,x^{i,1}_{k,i}\) are not the same. Let us suppose, without loss of generality, that the assignment to \(x^{i,1}_{1,i}\) and \(x^{i,1}_{2,i}\) are different. In other words, we have that \(x^{i}_{1,i}\
eq x^{i}_{2,i}\), where we think of \(x^{i}_{1,i},x^{i}_{2,i}\) as \(\log n\) bit vectors. Let \(\Delta\subseteq[\ell]\) such that \(\beta\in\Delta\) if and only if \(\mathcal{E}_{C_{\ell}}(x^{i}_{1,i})_{\beta}\
eq\mathcal{E}_{C_{\ell}}(x^{i}_{2,i })_{\beta}\). By the distance of the code \(C_{\ell}\) we have that \(|\Delta|\geq\delta\ell\). Finally, notice that for all \(\beta\in\Delta\), we have that the assignment does not satisfy constraint \(P_{\beta}\) in \(\mathcal{P}^{\prime\prime}\). We refer to the problem of distinguishing if there is an assignment to \(X\) such that all the constraints are satisfied or if every assignment to \(X\) does not satisfy a constant fraction of the constraints, as the \(k\)-Cap CSP problem. In order to rule out \(F(k)\) approximation FPT algorithms for \(k\)-Dominating Set, we will need that for every assignment to \(X\) that violates at least one constraint in \(\mathcal{P}^{\prime}\), we have that the same assignment violates at least \(\alpha\) fraction of the constraints in \(\mathcal{P}^{\prime\prime}\) (instead of just \(\delta\); note that \(\alpha\) is very close to \(1\), whereas \(\delta\) can be at most half). To boost the gap [37] we apply a simple repetition/direct-product trick to our constraint system. Starting from \(\mathcal{P}^{\prime\prime}\), we construct a new set of constraints \(\mathcal{P}^{*}\), on the same variable set \(X\), as follows. \[\mathcal{P}^{*}:=\{P_{\mathrm{S}}\mid S\in[\ell]^{t}\},\]  
where \(t=\frac{\log(1-\alpha)}{\log(1-\delta)}\). For every \(S\in[\ell]^{t}\), we define \(P_{\mathrm{S}}\) to be satisfied if and only if for all \(\beta\in S\), the constraint \(P_{\beta}\) is satisfied. It is easy to see that \(\mathcal{P}^{\prime\prime}\) and \(\mathcal{P}^{*}\) have the same set of completely satisfying assignments. However, for every assignment to \(X\) that violates \(\delta\) fraction of constraints in \(\mathcal{P}^{\prime\prime}\), we have that the same assignment violates at least \(\alpha\) fraction of the constraints in \(\mathcal{P}^{*}\). To see this, consider an assignment that violates \(\delta\) fraction of constraints in \(\mathcal{P}^{\prime\prime}\), say it violates all constraints \(P_{\beta}\in\mathcal{P}^{\prime\prime}\), for every \(\beta\in\Delta\subseteq[\ell]\). This implies that the assignment satisfies constraint \(P_{\mathrm{S}}\) if and only if \(S\in([\ell]\setminus\Delta)^{t}\). This implies that the fraction of constraints in \(\mathcal{P}^{*}\) that the assignment can satisfy is upper bounded by \((1-\delta)^{t}=1-\alpha\).