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), relies on a well-known L-reduction from Set Cover to Dominating Set (also reported on Wikipedia), 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)?

andall the subsets. The subsets constitute part of the input for Set Cover. $\endgroup$ – mhum May 6 '13 at 23:11