# Set Cover with Multiple covers

I am interested in whether a set cover instance that covers all elements $$q$$ times may have the property that every sufficiently small subset of this set cover will not cover the elements even once. More formally, let $$E = \{e_1,e_2,\ldots,e_m\}$$ be a set of elements and let $$q \in \mathbb{N}$$ be some parameter. I am interested in verifying if one can construct sets $$X = \{S_1,\ldots,S_n\} \subseteq 2^E$$ such that the following holds, for some constant $$\alpha \in (0,1)$$ (independent of $$m,n,q$$).

(1) Every element is covered $$q$$ times. Namely, for each $$e_i, i\in \{1,2,\ldots,m\}$$ there are $$q$$ (different) sets $$S_{j_1},\ldots,S_{j_q} \in X$$ such that $$e_i \in S_{j_k}$$ for $$k \in \{1,2,\ldots,q\}$$.

(2) Every subset of $$X$$ of at most $$\alpha \cdot n$$ sets does not cover all elements (once). That is, for every $$Y \subseteq X$$ such that $$|Y| \leq \alpha \cdot n$$ there is $$e_i, i\in \{1,2,\ldots,m\}$$ such that for all $$S \in Y$$ it holds that $$e_i \notin S$$.

Does a similar construction exist in the literature? any thoughts or references would be appreciated.

• Yes, such constructions exist. These are related to integrality gap and hardness for Set Cover with bounded frequency etc. See this earlier post and pointers. cstheory.stackexchange.com/questions/191/… Jan 5 at 19:31
• I do not quite understand the relation to Set Cover with bounded frequency. Which of the papers mentioned gives such a construction? thanks in advance.
– John
Jan 6 at 18:04

This answer expands on Chandra's comment. We'll prove two lemmas that show that $$q=O(\log m)$$ is a necessary condition for Properties (1) and (2) to hold, and that this bound is tight in the sense that there are infinitely many instances $$X$$ having Properties (1) and (2) with $$q=\Theta(\log m)$$. The proofs use known Set-Cover LP integrality gaps, per Chandra's comment.

Lemma 1. If Properties (1) and (2) hold, then $$q = O(\log m)$$.

Lemma 2. There are infinitely many instances $$X$$ such that (1) and (2) hold and $$q= \Omega(\log m)$$.

For the proofs, fix any $$(m, n, q, \alpha)$$ and "instance" $$X$$ as in the post. Let LP denote the standard linear-program relaxation of the standard integer linear program for the Set Cover instance defined by the set system $$X$$ (in which each element must be covered at least once).

Proof of Lemma 1. Let $$\overline X$$ be the (fractional) LP solution that gives weight $$1/q$$ to each set in $$X$$. By Property (1), $$\overline X$$ is feasible for the LP. It is well-known that the integrality gap of the LP is at most $$H_m$$. (This is provable by, e.g., randomized rounding or the standard greedy algorithm.) So there is a set cover of size at most $$H_m$$ times the size of $$\overline X$$, that is, at most $$H_m |X|/ q = H_m n/ q$$. By Property (2), then, $$H_m n/q > \alpha n$$. That is, $$q < H_m / \alpha$$. Since $$\alpha$$ is a positive constant, $$q= O(\log m)$$. $$~~~\Box$$

Proof of Lemma 2. Now fix any particular Set-Cover instance for which the integrality gap of the LP is achieved (that is, any set cover for the instance has size at least $$H_m$$ times the value of the LP for the instance). (It is well known that there are infinitely many such instances.) Let $$\overline X$$ be an optimal fractional solution for the LP for this instance.

By definition of the integrality gap, any set cover for the instance has size at least $$\overline n = \lceil |\overline X|H_m\rceil$$, where $$|\overline X|=\sum_s \overline X_s$$ is the value of $$\overline X$$.

Let $$X$$ be the random multiset obtained by taking, say, $$n = 100\overline n$$ sets i.i.d. from the distribution $$\overline X / |\overline X|$$. Then $$|X| = n = 100\overline n$$, and by the previous paragraph, Property (2) holds for $$X$$ with $$\alpha = 1/101$$.

Let $$q$$ be the minimum, over all elements $$e$$, of the number of sets in $$X$$ that contain $$e$$. So $$X$$ satisfies Property (1) for this $$q$$. We claim that with positive probability $$q \ge 80 \ln m$$ (as needed for the lemma).

It remains only (i) to show this claim, and (ii) to argue that without loss of generality we can assume that, as stipulated in the post, $$X$$ is a set (rather than a multi-set).

(i) This follows from standard results about the integrality gap of the standard linear-program relaxation for set multi-cover. But here is a self-contained argument:

Fix any element $$e$$. Recall that $$\overline X$$ is a fractional set cover. So, with each sample added to $$X$$, the probability that $$e$$ is covered is at least $$1/|\overline X|$$. So the expected number of sets in $$X$$ that cover $$e$$ is at least $$n/|\overline X| = 100\overline n/|\overline X| \ge 100 H_m$$. By a standard Chernoff bound, the probability that this number is less than $$80 H_m = (1-1/5) 100 H_m$$ is at most $$\exp(-(1/5)^2 100 H_m/3) < \exp(-(33/25) \ln m) = o(1/m).$$ Now, by the naive union bound (summing over the $$m$$ elements $$e$$), the probability that $$X$$ fails to cover every element at least $$80 H_m$$ times is $$o(1)$$. This shows the claim.

(ii) Without loss of generality assume that no set occurs in $$X$$ more than $$q$$ times (otherwise simply reduce the number of copies to $$q$$; Properties (1) and (2) will still hold). Let $$A$$ be a set of $$q$$ new artificial elements. Modify $$X$$ as follows. Add all the elements of $$A$$ to every set in $$X$$, then, for each set $$s$$ that occurs more than once in $$X$$, remove a distinct element of $$A$$ from each copy of $$s$$ except the first. Let $$X'$$ be the resulting set family. By construction all sets in $$X'$$ are distinct. Property (2) holds for $$X'$$ because it holds for $$X$$. For $$X'$$, Property (1) holds for each original element because $$X$$ has Property (1). Property (1) holds for each artificial element because each artificial element is in at least $$m-d_2$$ sets, where $$d_2$$ is the number of distinct sets that occur more than once in $$X$$, so that $$d_2 \le m/2$$, so that each artificial element is in at least $$m-d_2 \ge m/2 \ge q$$ sets in $$X'$$ (using here that $$q = O(\log m)$$). So $$X'$$ has the desired properties. $$~~~\Box$$