Set Cover with Multiple covers

Question

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.

Answer 1

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$