# 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
From \(k\)-Gap CSP to gap \(k\)-Dominating SetIn the second part, starting from the aforementioned instance of \(k\)-Gap CSP (after boosting the gap), we construct an instance \(H\) of \(k\)-Dominating SetThe construction is due to Feige [29; 38] and it proceeds as follows. Let \(\mathcal{F}\) be the set of all functions from \(\{0,1\}^{ik}\) to \(\binom{k}{2}\), i.e., \(\mathcal{F}:=\{f:\{0,1\}^{ik}\to\binom{k}{2}\}\). The graph \(H\) is on vertex set \(U=A\cup B\), where \(A=\mathcal{P}^{*}\times\mathcal{F}\) and \(B=E(G)\), i.e., \(B\) is simply the edge set of \(G\). We introduce an edge between all pairs of vertices in \(B\). We introduce an edge between \(a:=(S:=(s_{1},\ldots,s_{t})\in[\ell]^{t},f:\{0,1\}^{tk}\to\binom{k}{2})\in A\) and \(e:=(v_{i},v_{j})\in E\) if and only if the following holds. \[\exists\tau:=(\tau_{1},\ldots,\tau_{t})\in\{0,1\}^{kt},\text{ such that }f(\tau)=\{i,j\}\text{ and }\] \[\forall\tau\in[t],\text{ we have }\mathcal{E}_{C_{\ell}}(v_{i})_{s_{\tau}}=( \tau_{t})_{i}\text{ and }\mathcal{E}_{C_{\ell}}(v_{j})_{s_{\tau}}=(\tau_{t})_{j}.\]  
Notice that the number of vertices in \(H\) is \(|A|+|B|\leq(\frac{\log n}{\rho})^{t}\cdot\binom{k}{2}^{2^{tk}}+n^{2}<\eta(k) \cdot n^{2.01}\), for some computable function \(\eta\). It is not hard to check that the following hold:  
* (Completeness) If there is an assignment to \(X\) that satisfies all constraints in \(\mathcal{P}^{*}\), then the corresponding \(\binom{k}{2}\) vertices in \(B\) dominate all vertices in the graph \(H\). * (Soundness) If each assignment can only satisfy \((1-\alpha)\) fraction of constraints in \(\mathcal{P}^{*}\), then any dominating set of \(H\) has size at least \(F\left(\binom{k}{2}\right)\cdot\binom{k}{2}\). We skip presenting details of this part of the proof here. The proofs have been derived many times in literature; if needed, the readers may refer to Appendix A of [35]. This completes our sketch of the proof of Theorem 4. A few remarks are in order. First, the \(k\)-Gap CSP problem described in the proof above, is formalized as the \(k\)-Maxcover problem in [35] (and was originally introduced in [39]). In particular, the formalism of \(k\)-Maxcover (which may be thought of as the parameterized label cover problem) is generic enough to be used as an intermediate gap problem to reduce to both \(k\)-Dominating Set (as in [35]) and \(k\)-Clique (as in [39]). Moreover, it was robust enough to capture stronger running time lower bounds (under stronger hypotheses); this will elaborated below. However, in order to keep the above proof succinct, we skipped introducing the \(k\)-Maxcover problem, and worked with \(k\)-Gap CSP, which was sufficient for the above proof. Second, Karthik C. S. et al. [35] additionally showed that for every computable functions \(T,F:\mathbb{N}\to\mathbb{N}\) and every constant \(\varepsilon>0\):  
* Assuming the Exponential Time Hypothesis (ETH), there is no \(F(k)\)-approximation algorithm for \(k\)-Dominating Set that runs in \(T(k)\cdot n^{o(k)}\) time. * Assuming the Strong Exponential Time Hypothesis (SETH), for every integer \(k\geq 2\), there is no \(F(k)\)-approximation algorithm for \(k\)-Dominating Set that runs in \(T(k)\cdot n^{k-\varepsilon}\) time. In order to establish Theorem 4 and the above two results, Karthik C. S. et al. [35] introduced a framework to prove parameterized hardness of approximation results. In this framework, the objective was to start from either the \(\mathsf{W}[1]\
eq\mathsf{FPT}\) hypothesis, ETH, or SETH, and end up with the gap \(k\)-Dominating Set, i.e., they design reductions from instances of \(k\)-Clique, 3-CNF-SAT, and \(\ell\)-CNF-SAT, to an instance of gap \(k\)-Dominating Set. A prototype reduction in this framework has two modular parts. In the first part, which is specific to the problem they start from, they generate a gap and obtain hardness of gap \(k\)-Maxcover.