# 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 second part, they show a gap preserving reduction from gap \(k\)-Maxcover to gap \(k\)-Dominating Set, which is essentially the same as the reduction from \(k\)-Gap CSP to \(k\)-Dominating Set in the proof of Theorem 4. The first part of a prototype reduction from the computational problem underlying a hypothesis of interest to gap \(k\)-Maxcover follows by the design of an appropriate communication protocol. In particular, the computational problem is first reduced to a constraint satisfaction problem (CSP) over \(k\) (or some function of \(k\)) variables over an alphabet of size \(n\). The predicate of this CSP would depend on the computational problem underlying the hypothesis from which we started. Generalizing ideas from [40], they then show how a protocol for computing this predicate in the multiparty (number of players is the number of variables of the CSP) communication model, can be combined with the CSP to obtain an instance of gap \(k\)-Maxcover. For example, for the \(\mathsf{W}[1]\
eq\mathsf{FPT}\) hypothesis and ETH, the predicate is a variant of the equality function, and for SETH, the predicate is the well studied disjointness function. The completeness and soundness of the protocols computing these functions translate directly to the completeness and soundness of \(k\)-Maxcover. Third, we recall that Lin [26] recently provided alternate proofs of Theorem 4 and the above mentioned stronger running time lower bounds. While we discussed about his proof technique in Section 3.1.1, we would like to discuss about his result here. Following the right setting of parameters in the proof of Theorem 4 (for example set \(\alpha=1-\frac{1}{(\log n)^{\Omega(1/k)}}\)), we can obtain that approximating \(k\)-Dominating Set to a factor of \((\log n)^{1/k^{3}}\) is \(\mathsf{W}[1]\)-hard. Lin improved the exponent of \(1/k^{3}\) in the approximation factor to \(h(k)\) for any computable function \(h\). Can this inapproximability be further improved? On the other hand, can we do better than the simple polynomial time greedy algorithm which provides a \((1+\ln n)\) factor approximation? This leads us to the following question:  
**Open Question 4** (Tight inapproximability of \(k\)-Dominating Set). : _Is there a \((\log n)^{1-o(1)}\) factor approximation algorithm for \(k\)-Dominating Set running in time \(n^{k-0.1}\)?_  
We conclude the discussion on \(k\)-Dominating Set with an open question on \(\mathsf{W}[2]\)-hardness of approximation. As noted earlier, \(k\)-Dominating Set is a \(\mathsf{W}[2]\)-complete problem, and Theorem 4 shows that the problem is \(\mathsf{W}[1]\)-hard to approximate to any \(F(k)\) factor. However, is there some computable function \(F\) for which approximating \(k\)-Dominating Set is in \(\mathsf{W}[1]\)? In other words we have:  
**Open Question 5** (\(\mathsf{W}[2]\)-completeness of approximating \(k\)-Dominating Set). : _Can we base total inapproximability of \(k\)-Dominating Set on \(\mathsf{W}[2]\
eq\mathsf{FPT}\)?_