# Why the reduction from MINIMUM SET COVER to MINIMUM DOMINATING SET means $c \log n$-inapproximability for MINIMUM DOMINATING SET

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.