<p>I didn't at first understand that the question <a href="https://cstheory.stackexchange.com/questions/8449/inapproximability-of-set-cover-can-i-assume-m-polyn">Inapproximability of set cover: can I assume m=poly(n)?</a> contains the answer to my own question. (Thanks to @Tsuyoshi Ito for pointing out.) </p>

<p>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.</p>

CC BY-SA 3.0
2012-05-26T19:02:21.367Z
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.
Suresh Venkat
CC BY-SA 4.0
2012-05-25T22:20:06.177Z
2018-05-18T13:59:38.753Z
2018-05-18T13:59:38.753Z
Yury Kartynnik
<p>There is a well-known reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET provided at <a href="http://en.wikipedia.org/wiki/Dominating_set#L-reductions" rel="nofollow">http://en.wikipedia.org/wiki/Dominating_set#L-reductions</a> (attributed there to Kann 1992, but seen, for example, in Paz and Moran, Non Deterministic Polynomial Optimization Problems and Their Approximations, 1981).</p>

<p>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 &gt; 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.</p>

<p>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?</p>

<p>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$.</p>

<p><em>Note</em>: <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node11.html" rel="nofollow">this page</a> in <strong>A compendium of NP optimization problems</strong> also cites Raz and Safra's result on SET COVER inapproximability as sufficient for ($c \log |V|$)-inapproximability for DOMINATING SET.</p>

CC BY-SA 3.0
2012-05-25T22:01:02.067Z
possible duplicate of [Inapproximability of set cover: can I assume m=poly(n)?](http://cstheory.stackexchange.com/questions/8449/inapproximability-of-set-cover-can-i-assume-m-polyn)
Tsuyoshi Ito
CC BY-SA 4.0
2020-04-07T04:09:44.497Z
@TsuyoshiIto Feel free to post your comment as an answer for me to accept it.
Yury Kartynnik
<cc.complexity-theory><approximation-hardness><reductions><set-cover>
Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET
Yury Kartynnik
# Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

(Asked by: username_0 on 2012-05-25)

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](http://www.nada.kth.se/~viggo/wwwcompendium/node11.html) 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.

**Tags:** cc.complexity-theory, approximation-hardness, reductions, set-cover

> **Comments:**
> **username_1**: possible duplicate of [Inapproximability of set cover: can I assume m=poly(n)?](http://cstheory.stackexchange.com/questions/8449/inapproximability-of-set-cover-can-i-assume-m-polyn)  
> **username_0**: @TsuyoshiIto Feel free to post your comment as an answer for me to accept it.  

---

## 1 answers

### Answer by username_0 on 2012-05-25. Score: 1 | Accepted answer

I didn't at first understand that the question [Inapproximability of set cover: can I assume m=poly(n)?](https://cstheory.stackexchange.com/questions/8449/inapproximability-of-set-cover-can-i-assume-m-polyn) contains the answer to my own question. (Thanks to @username_1 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.

> **Comments:**
> **username_2**: 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.  

---

