# Is this a proof that SET COVER is not an NP-hard problem?

In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows:

Set Cover Problem. Let $X = \{x_1, \ldots, x_k\}$ be a finite set and $P = \{p_1, \ldots, p_m\} \subseteq 2^X$ be a family of its subsets. Find minimum size sub-family $M$ of $P$ such that $X \subseteq \bigcup \{p \mid p \in M\}$.

An instance of the set cover problem is $\epsilon$-dense if there is $\epsilon > 0$ such that any element of $X$ belongs to at least $\epsilon \, m$ sets from $P$. We show that the dense set cover problem can be approximated with the performance ratio $c \log k$ for any $c > 0$ though it is unlikely to be NP-hard.

In page 3, Lemma 2.1 implies—and Theorem 2.2 proves—that $\epsilon$-DENSE SET COVER is not NP-hard. But, since SET COVER is $\frac{1}{m}$-DENSE SET COVER (any element of $X$ belongs to at least 1 of the $m$ sets), would this mean that SET COVER is not NP-hard?

• Their definition is bad, not capturing what they mean. (For every instance of set cover there exists an $\epsilon$ so that it is $\epsilon$-dense....) They mean to define a new problem for every fixed $\epsilon$, which is the $\epsilon$-dense set cover problem, and they mean to define it to be set cover with the promise that all inputs are $\epsilon$-dense for that fixed, constant $\epsilon$.
– usul
Apr 8, 2016 at 11:41

Weighting of elements from set $P$ of SET COVER problem can be obtained by solving a system of linear inequalities for a given $\varepsilon$ that involves $\{0,1\}$-matrix $I=[x_i\in P_j]:$ $Iw\geq\varepsilon\sum\limits_{i=1}^mw_i.$ If it is not feasible then $\varepsilon$-DENSE SET COVER is void. Found weighting can be easily removed by repeating elements of $P$ with respect to the weighting but the resulting problem will be the same. Feasible SET COVER could be reduced to dense one for $\varepsilon=\frac{1}{m}$ but generally aforementioned reduction could lead to void dense problem for constant $\varepsilon.$

In the geometric case when VC-dimension is finite the dense problem with constant $\varepsilon$ could be solved in polynomial time due to result of Haussler and Welzl "epsilon-nets and simplex range queries" claiming existence of feasible solution to $\varepsilon$-dense problem of length $$\frac{8d}{\varepsilon}\log\frac{d}{\varepsilon}.$$ Having upper bound on the problem optimum we could solve te problem by brute-force search. Here $d$ denotes VC-dimension.

• So those SET COVER instances for which the system of linear inequalities (for the corresponding $\varepsilon = \frac{1}{m}$) is feasible would be solved optimally in polynomial time, wouldn't they? Otherwise, SET COVER remains NP-hard. Apr 8, 2016 at 10:49
• I think you misunderstood something in Karpinski book. It is always true that SET COVER is $\frac{1}{m}$-dense otherwise some element of $X$ could not be covered. The system is $Iw\geq\varepsilon\sum\limits_{i=1}^m w_i.$ What I say is the reduction of unweighted SET COVER to dense one given $\varepsilon.$
– KKS
Apr 8, 2016 at 11:10
• Alright, so SET COVER $\leq_\mathrm{P}$ $\varepsilon$-DENSE SET COVER, according to your reduction. If that is true, and since we know that SET COVER is NP-hard, how is that they say that $\varepsilon$-DENSE SET COVER is unlikely to be NP-hard? That's what I don't understand. Apr 8, 2016 at 11:20
• I think that they mean constant $\varepsilon.$ In this case the reduction fails as there are instances of SET COVER that lead to void instance of dense one.
– KKS
Apr 8, 2016 at 11:33
• OK, silly me! haha. Thank you, thank you very much for your help :) Apr 8, 2016 at 11:36