Hardness of approximation of Dominating Set

Question

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)?

Answer 1

I had a private conversation with Dana Moshkovitz (whom I thank), who confirmed that, in Alon, Moshkovitz, and Safra (2006), 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.

Answer 2

I have a partial answer (thanks to Uriel Feige for pointing this out), but the main problem is still open.

According to Feige (1998), it is quasi-$NP$-hard to approximate Set Cover within a ratio of $(1-o(1))\ln n$ and, in all the hard Set Cover instances, $n>m$ holds. Hence, after the reduction to Dominating Set, the number of vertices is at most $2n$, which implies once again an $\Omega(\log n)$ lower bound.

Of course, this does not completely answer my question, because it only shows quasi-$NP$-hardness (i.e., the approximation ratio is not achievable in polynomial time unless $NP\subset TIME(n^{{\rm polylog}\ n})$), as opposed to $NP$-hardness.

The current state of the art for Set Cover, obtained by Alon, Moshkovitz, and Safra (2006), is that it is $NP$-hard to approximate within a $c\cdot \log n$ factor. Even after inspecting their construction, it is not clear to me if $n>m$ can be inferred for all hard Set Cover instances, as well. Actually, even $n^\lambda >m$ would suffice, for some $\lambda\geqslant 1$. A related paper by Raz and Safra (1997) claims a similar result, but with a lower constant factor $c$. However, I cannot find any proof of this claim. If anyone can find it, it can be checked if $n^\lambda >m$ at least there.