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.

  • $\begingroup$ 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/… $\endgroup$ Jan 5 at 19:31
  • $\begingroup$ 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. $\endgroup$
    – John
    Jan 6 at 18:04

1 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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.