6
$\begingroup$

There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at http://en.wikipedia.org/wiki/Dominating_set#L-reductions (attributed there to Kann 1992, but seen, for example, in Paz and Moran, Non Deterministic Polynomial Optimization Problems and Their Approximations, 1981).

I've seen several claims (for example, Lund and Yannakakis, On the Hardness of Approximating Minimization Problems, 1994) that this reduction means the approximation factor bound of $c \log m$ for some $c > 0$ (proven in Raz and Safra, A sub-constant error-probability low-degree test, and sub-constant error-probability PCP characterization of NP, 1997 and cited in the mentioned Wikipedia article) gives a similar bound of $c \log n$ for MINIMUM DOMINATING SET.

But $m$ in the MINIMUM SET COVER bound is the cardinality of the universe of the sets, while the size $n = |V|$ of the graph obtained by the reduction is bigger by the number of the subsets provided for covering. When the number of subsets gets as large as $2^m$, $\log n = \log (m + 2^m)$ becomes $\Theta(m)$. How do we prove the $c \log m$ approximation factor for SET COVER when the DOMINATING SET approximation differs from the optimum only by a factor of $c m$ in the worst case?

One might argue that subsets contained in other subsets are redundant - but this still leaves $m \choose {\lfloor m/2\rfloor}$ subsets due to the Sperner's theorem, which is yet of the order of $2^m$.

Note: this page in A compendium of NP optimization problems also cites Raz and Safra's result on SET COVER inapproximability as sufficient for ($c \log |V|$)-inapproximability for DOMINATING SET.

$\endgroup$
1
$\begingroup$

I didn't at first understand that the question Inapproximability of set cover: can I assume m=poly(n)? contains the answer to my own question. (Thanks to @Tsuyoshi Ito for pointing out.)

In short, the proof by Raz and Safra (and any other PCP-based proof) builds an instance of SET COVER where the number of subsets is a polynomial of the universe cardinality.

$\endgroup$
  • $\begingroup$ There are three options. We could close this as a duplicate, OR @TsuyoshiIto could post his comment as an answer OR you could accept your own answer. $\endgroup$ – Suresh Venkat May 26 '12 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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