Return to Answer

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 a $\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.

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.

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 a $\Omega(\log n)$ lower bound (just with a worse constant factor than claimed in the literature).

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.

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 a $\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.

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 a $\Omega(\log n)$ lower bound (just with a worse constant factor than claimed in the literature).

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. By 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.

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 a $\Omega(\log n)$ lower bound (just with a worse constant factor than claimed in the literature).

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.