<p>This answer expands on Chandra's comment.  We'll prove two lemmas that show that <span class="math-container">$q=O(\log m)$</span> 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 <span class="math-container">$X$</span> having Properties (1) and (2) with <span class="math-container">$q=\Theta(\log m)$</span>.  The proofs use known Set-Cover LP integrality gaps, per Chandra's comment.</p>
<p><strong>Lemma 1.</strong> <em>If Properties (1) and (2) hold, then <span class="math-container">$q = O(\log m)$</span>.</em></p>
<p><strong>Lemma 2.</strong> <em>There are infinitely many instances <span class="math-container">$X$</span> such that (1) and (2) hold and <span class="math-container">$q= \Omega(\log m)$</span>.</em></p>
<p>For the proofs, fix any <span class="math-container">$(m, n, q, \alpha)$</span> and &quot;instance&quot; <span class="math-container">$X$</span> 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 <span class="math-container">$X$</span> (in which each element must be covered at least <em>once</em>).</p>
<p><em>Proof of Lemma 1.</em> Let <span class="math-container">$\overline X$</span> be the (fractional) LP solution that gives weight <span class="math-container">$1/q$</span> to each set in <span class="math-container">$X$</span>.  By Property (1), <span class="math-container">$\overline X$</span> is feasible for the LP.  It is well-known that the integrality gap of the LP is at most <span class="math-container">$H_m$</span>. (This is provable by, e.g., randomized rounding or the standard greedy algorithm.)  So there is a set cover of size at most <span class="math-container">$H_m$</span> times the size of <span class="math-container">$\overline X$</span>, that is, at most <span class="math-container">$H_m |X|/ q = H_m n/ q$</span>.
By Property (2), then, <span class="math-container">$H_m n/q &gt; \alpha n$</span>.  That is, <span class="math-container">$q &lt; H_m / \alpha$</span>.  Since <span class="math-container">$\alpha$</span> is a positive constant, <span class="math-container">$q= O(\log m)$</span>. <span class="math-container">$~~~\Box$</span></p>
<p><em>Proof of Lemma 2.</em> 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 <span class="math-container">$H_m$</span> times the value of the LP for the instance). (It is well known that there are infinitely many such instances.)
Let <span class="math-container">$\overline X$</span> be an optimal fractional solution for the LP for this instance.</p>
<p>By definition of the integrality gap,
any set cover for the instance has size at least <span class="math-container">$\overline n = \lceil |\overline X|H_m\rceil$</span>,
where <span class="math-container">$|\overline X|=\sum_s \overline X_s$</span> is the value of <span class="math-container">$\overline X$</span>.</p>
<p>Let <span class="math-container">$X$</span> be the random multiset obtained by taking,
say, <span class="math-container">$n = 100\overline n$</span> sets i.i.d.
from the distribution <span class="math-container">$\overline X / |\overline X|$</span>.
Then <span class="math-container">$|X| = n = 100\overline n$</span>,
and by the previous paragraph,
Property (2) holds for <span class="math-container">$X$</span> with <span class="math-container">$\alpha = 1/101$</span>.</p>
<p>Let <span class="math-container">$q$</span> be the minimum, over all elements <span class="math-container">$e$</span>, of the number of sets in <span class="math-container">$X$</span> that contain <span class="math-container">$e$</span>.  So <span class="math-container">$X$</span> satisfies Property (1) for this <span class="math-container">$q$</span>.
We claim that <em>with positive probability <span class="math-container">$q \ge 80 \ln m$</span></em> (as needed for the lemma).</p>
<p>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, <span class="math-container">$X$</span> is a set (rather than a multi-set).</p>
<p>(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:</p>
<p>Fix any element <span class="math-container">$e$</span>.  Recall that <span class="math-container">$\overline X$</span> is a fractional set cover.  So, with each sample added to <span class="math-container">$X$</span>, the probability that <span class="math-container">$e$</span> is covered is at least <span class="math-container">$1/|\overline X|$</span>.  So the expected number of sets in <span class="math-container">$X$</span> that cover <span class="math-container">$e$</span> is at least <span class="math-container">$n/|\overline X| = 100\overline n/|\overline X| \ge 100 H_m$</span>.  By a standard Chernoff bound, the probability that this number is less than <span class="math-container">$80 H_m = (1-1/5) 100 H_m$</span> is at most
<span class="math-container">$$\exp(-(1/5)^2 100 H_m/3) &lt; \exp(-(33/25) \ln m) = o(1/m).$$</span>
Now, by the naive union bound (summing over the <span class="math-container">$m$</span> elements <span class="math-container">$e$</span>), the probability that <span class="math-container">$X$</span> fails to cover every element at least <span class="math-container">$80 H_m$</span> times is <span class="math-container">$o(1)$</span>.  This shows the claim.</p>
<p>(ii) Without loss of generality assume that no set occurs in <span class="math-container">$X$</span> more than <span class="math-container">$q$</span> times (otherwise simply reduce the number of copies to <span class="math-container">$q$</span>; Properties (1) and (2) will still hold).  Let <span class="math-container">$A$</span> be a set of <span class="math-container">$q$</span> new artificial elements.  Modify <span class="math-container">$X$</span> as follows.  Add all the elements of <span class="math-container">$A$</span> to every set in <span class="math-container">$X$</span>, then, for each set <span class="math-container">$s$</span> that occurs more than once in <span class="math-container">$X$</span>, remove a distinct element of <span class="math-container">$A$</span> from each copy of <span class="math-container">$s$</span> except the first.  Let <span class="math-container">$X'$</span> be the resulting set family.  By construction all sets in <span class="math-container">$X'$</span> are distinct.  Property (2) holds for <span class="math-container">$X'$</span> because it holds for <span class="math-container">$X$</span>.
For <span class="math-container">$X'$</span>, Property (1) holds for each <em>original</em> element because <span class="math-container">$X$</span> has Property (1).  Property (1) holds for each artificial element because each artificial element is in at least <span class="math-container">$m-d_2$</span> sets, where <span class="math-container">$d_2$</span> is the number of distinct sets that occur more than once in <span class="math-container">$X$</span>, so that <span class="math-container">$d_2 \le m/2$</span>, so that each artificial element is in at least <span class="math-container">$m-d_2 \ge m/2 \ge q$</span> sets in <span class="math-container">$X'$</span> (using here that <span class="math-container">$q = O(\log m)$</span>).  So <span class="math-container">$X'$</span> has the desired properties. <span class="math-container">$~~~\Box$</span></p>

CC BY-SA 4.0
2024-01-09T14:39:26.207Z
2024-01-09T14:39:26.207Z
Neal Young
<p>I am interested in whether a set cover instance that covers all elements <span class="math-container">$q$</span> times may have the property that every sufficiently small subset of this set cover will not cover the elements even once. More formally, let <span class="math-container">$E = \{e_1,e_2,\ldots,e_m\}$</span> be a set of elements and let <span class="math-container">$q \in \mathbb{N}$</span> be some parameter. I am interested in verifying if one can construct sets <span class="math-container">$X = \{S_1,\ldots,S_n\} \subseteq 2^E$</span> such that the following holds, for some constant <span class="math-container">$\alpha \in (0,1)$</span> (independent of <span class="math-container">$m,n,q$</span>).</p>
<p>(1) Every element is covered <span class="math-container">$q$</span> times. Namely, for each <span class="math-container">$e_i, i\in \{1,2,\ldots,m\}$</span> there are <span class="math-container">$q$</span> (different) sets <span class="math-container">$S_{j_1},\ldots,S_{j_q} \in X$</span> such that <span class="math-container">$e_i \in S_{j_k}$</span> for <span class="math-container">$k \in \{1,2,\ldots,q\}$</span>.</p>
<p>(2) Every subset of <span class="math-container">$X$</span> of at most <span class="math-container">$\alpha \cdot n$</span> sets does not cover all elements (once). That is, for every <span class="math-container">$Y \subseteq X$</span> such that <span class="math-container">$|Y| \leq \alpha \cdot n$</span> there is <span class="math-container">$e_i, i\in \{1,2,\ldots,m\}$</span> such that for all <span class="math-container">$S \in Y$</span> it holds that <span class="math-container">$e_i \notin S$</span>.</p>
<p>Does a similar construction exist in the literature? any thoughts or references would be appreciated.</p>

CC BY-SA 4.0
2024-01-05T19:31:36.370Z
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. https://cstheory.stackexchange.com/questions/191/bounded-cardinality-bounded-frequency-set-cover-hardness-of-approximation
Chandra Chekuri
CC BY-SA 4.0
2024-01-06T18:04:03.350Z
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
<np-hardness><reductions><approximation-hardness><set-cover>
Set Cover with Multiple covers
John
# Set Cover with Multiple covers

(Asked by: username_0 on 2024-01-05)

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.

**Tags:** np-hardness, reductions, approximation-hardness, set-cover

> **Comments:**
> **username_1**: 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. https://cstheory.stackexchange.com/questions/191/bounded-cardinality-bounded-frequency-set-cover-hardness-of-approximation  
> **username_0**: 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.  

---

## 1 answers

### Answer by username_2 on 2024-01-09. Score: 2 | Accepted answer

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$


---

