5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ If I understand your objection correctly, I think this issue may be resolved by observing that the problem size of Set Cover is related to the size of the universe set and all the subsets. The subsets constitute part of the input for Set Cover. $\endgroup$
    – mhum
    May 6, 2013 at 23:11
  • $\begingroup$ Using my notation, the problem size of Set Cover is $m\cdot n$. This is correct, but all the approximation bounds are always given just in terms of $n$. That is, there is a greedy algorithm that achieves a $\ln n$ approximation ratio (no $m$ involved), and it is NP-hard to achieve a $c\cdot\log n$ approximation ratio (no $m$ involved). Hence, when reducing to Dominating Set, $n$ cannot be the number of vertices, but should be its logarithm. $\endgroup$ May 7, 2013 at 1:51
  • $\begingroup$ I stand corrected. The approximation ratios for Set Cover do appear to be independent of the number of sets. I'm not sure why I thought otherwise. $\endgroup$
    – mhum
    May 7, 2013 at 15:19
  • $\begingroup$ I agree this is sort of confusing. I guess this is why people tend to say nonchalantly that Set Cover and Dominating Set are equivalent as approximation problems (because they L-reduce to each other), and THEREFORE Dominating Set is not approximable within $\Omega(\log n)$, either. Well, these are two different $n$'s, so we should pay attention... $\endgroup$ May 7, 2013 at 17:48

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.