Given a graph G on n vertices with a promise that G has a dominating set of size k, is there a t(k) * poly(n) time algorithm that outputs a dominating set of size f(k) * k?
We will give a negative answer to this question by showing that unless FPT=W[1] such algorithm does not exist. We further rule out n^{o(k)}-time and n^{k-c}-time (log n)^{1/poly(k)}-approximation algorithms for k-Dominating Set for any c>0 under ETH and SETH, respectively.
Our results are obtained by establishing a connection between communication complexity and hardness of approximation, generalizing the ideas from a recent breakthrough work of
Abboud et al. [FOCS, 2017].