It is stated throughout the computational complexity literature that the Dominating Set problem is NP-hard to approximate within a factor of $\Omega(\log n)$. To my knowledge, the first and only proof available ([Lund and Yannakakis, 1994](ftp://ftp-sop.inria.fr/coati/personnel/Stephane.Perennes/LuYa94.pdf)), relies on a well-known L-reduction from Set Cover to Dominating Set (also reported on [Wikipedia](http://en.wikipedia.org/wiki/Dominating_set#L-reductions)), which implies that the two problems are equivalent in terms of approximation ratio. Because Set Cover is NP-hard to approximate within a factor of $\Omega(\log n)$, the same holds for Dominating Set.


I have reasons to believe that this may be an incorrect deduction.


Recall that, in Set Cover, the parameter $n$ is the size of the universe set. In contrast, the number of sets given as input, $m$, could be exponentially larger than $n$. Because the L-reduction from Set Cover to Dominating Set constructs a graph on $n+m$ vertices, this graph may have size exponential in $n$. Now, in Dominating Set, the "$n$" that is used in approximation bounds is in fact the number of vertices. It follows that, using this reduction, only a ratio of $O(\log \log n)$ can be deduced for Dominating Set, as opposed to $\Omega(\log n)$.


Can this proof be fixed in some easy way (or is my reasoning incorrect)?



Hardness of approximation of Dominating Set
I had a private conversation with Dana Moshkovitz (whom I thank), who confirmed that, in [Alon, Moshkovitz, and Safra (2006)](http://www.tau.ac.il/~nogaa/PDFS/GPGames.pdf), the hard instances of Set Cover resulting from a rather involved gap-preserving reduction are all such that $m\leqslant {\rm poly}(n)$. Hence, after the L-reduction to Dominating Set, we have graphs on $|V|$ vertices, such that $|V|=n+m\leqslant a\cdot n^k+b$, for some constants $a>0$, $b\geqslant 0$, $k\geqslant 1$. It follows that, since Set Cover is $NP$-hard to approximate within a factor of $\Omega(\log n)$, Dominating Set is $NP$-hard to approximate within a factor of $$\Omega(\log n) = \Omega\left(\log\left(\frac{|V|-b}{a}\right)^{\frac 1k}\right)= \Omega\left(\frac{\log(|V|-b)-\log a}{k}\right)=\Omega(\log |V|).$$ Determining optimal values for $a$, $b$, $k$ remains open.


It is my understanding that these matters have been overlooked by most authors, as no explicit mention to them is ever made, to the best of my knowledge. Usually it is just stated that Set Cover and Dominating Set are "equivalent" under L-reductions, hence the $c\cdot\log n$ hardness carries over to Dominating Set. Even the observation of the crucial inequality $m\leqslant {\rm poly}(n)$ resulting from the reductions to Set Cover has often been neglected by most authors (Feige being an exception), as well as the determination of an optimal constant factor for the hardness of approximation of Dominating Set.


