# 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  
In the \(k\)-Dominating Set problem we are given an integer \(k\) and a graph \(G\) on \(n\) vertices as input, and the goal is to determine if there is a dominating set of size at most \(k\). It was a long standing open question to design an algorithm which runs in time \(T(k)\cdot\operatorname{poly}(n)\) (i.e., FPT-time), that would find a dominating set of size at most \(F(k)\cdot k\) whenever the graph \(G\) has a dominating set of size \(k\), for any computable functions \(T\) and \(F\). The first non-trivial progress on this problem was by Chen and Lin [25] who ruled out the existence of such algorithms (under \(\operatorname{W}[1]\
eq\operatorname{FPT}\)) for all constant functions \(F\) (i.e., \(F(n)=c\), where \(c\) is any universal constant). We discussed their proof technique in the previous subsubsection. A couple of years later, Karthik C. S. et al. [35] completely settled the question, by ruling out the existence of such an algorithm (under \(\operatorname{W}[1]\
eq\operatorname{FPT}\)) for any computable function \(F\). Thus, \(k\)-Dominating Set was shown to be totally inapproximable. We elaborate on their proof below. **Theorem 4** ([35]). : _Let \(F:\mathbb{N}\to\mathbb{N}\) be any computable function. Given an instance \((G,k)\) of \(k\)-Dominating Set as input, it is \(\operatorname{W}[1]\)-hard to distinguish between the following two cases:_  
* _Completeness:_ \(G\) _has a dominating set of size_ \(k\)_._
* _Soundness: Every dominating set of_ \(G\) _is of size at least_ \(F(k)\cdot k\)_._  
The overall proof follows by reducing \(k\)-Multicolor Clique to the gap \(k\)-Dominating Set with parameters as given in the theorem statement. In the \(k\)-Multicolor Clique problem, we are given an integer \(k\) and a graph \(G\) on vertex set \(V:=V_{1}\dot{\cup}V_{2}\dot{\cup}\cdots\dot{\cup}V_{k}\) as input, where each \(V_{i}\) is an independent set of cardinality \(n\), and the goal is to determine if there is a clique of size \(k\) in \(G\). Following a straightforward reduction from the \(k\)-Clique problem, it is fairly easy to see that \(k\)-Multicolor Clique is W[1]-hard. The reduction from \(k\)-Multicolor Clique to the gap \(k\)-Dominating Set proceeds in two steps. In the first step we reduce \(k\)-Multicolor Clique to \(k\)-Gap CSP. This is the step where we generate the gap. In the second step, we reduce \(k\)-Gap CSP to gap \(k\)-Dominating Set. This step is fairly standard and mimics ideas from Feige's proof of the NP-hardness of approximating the Max Coverage problem [29]. Before we proceed with the details of the above two steps, let us introduce a small technical tool from coding theory that we would need. We need codes known in literature as good codes, these are binary error correcting codes whose rate and relative distances are both constants bounded away from \(0\) (see [36] (Appendix E.1.2.5) for definitions). The reader may think of them as follows: for every \(\ell\in\mathbb{N}\), we say that \(C_{\ell}\subseteq\{0,1\}^{\ell}\) is a good code if (i) \(|C_{\ell}|=2^{\rho\ell}\), for some universal constant \(\rho>0\), (ii) for any distinct \(c,c^{\prime}\in C_{\ell}\) we have that \(c\) and \(c^{\prime}\) have different values on at least \(\delta\ell\) fraction of coordinates, for some universal constant \(\delta>0\). An encoding of \(C_{\ell}\) is an injective function \(\mathcal{E}_{C_{\ell}}:\{0,1\}^{\rho\ell}\to C_{\ell}\). The encoding is said to be efficient if \(\mathcal{E}_{C_{\ell}}(x)\) can be computed in \(\operatorname{poly}(\ell)\) time for any \(x\in\{0,1\}^{\rho\ell}\). Let us fix \(k\in\mathbb{N}\) and \(F:\mathbb{N}\to\mathbb{N}\) as in the theorem statement.