<p>[<em>EDIT</em>: Added second proof, using Hall's theorem.]</p>
<hr />
<p><strong>Theorem 1.</strong> <em>There is a poly-time algorithm for the problem.</em></p>
<p>We give a direct proof, then another proof using <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem" rel="nofollow noreferrer">Hall's theorem</a>.</p>
<p>Both proofs use the following utility lemma,
which recasts the problem into a more convenient form.</p>
<p>Fix a problem instance <span class="math-container">$(S_1, S_2, \ldots, S_n)$</span>.
The problem is to decide
whether the instance is <em>feasible</em>,
meaning that there exists <span class="math-container">$C\subseteq [n]$</span>
such that <span class="math-container">$n-1 \ge |C| = |\bigcup_{i\in C} S_i| \ge 1$</span>.</p>
<p>If there is a set <span class="math-container">$S_i$</span> of size 1, the instance is feasible
(take <span class="math-container">$C=\{i\}$</span>), so assume otherwise.
Note that in the definition above
WLOG we can restrict to collections <span class="math-container">$C$</span>
containing at least one index <span class="math-container">$a$</span> with <span class="math-container">$|S_a| \ge 2$</span>,
and <em>not</em> containing at least one other index <span class="math-container">$b\in[n]$</span>.</p>
<p>Given <span class="math-container">$(a,b)\in [n]\times [n]$</span> with <span class="math-container">$|S_a| \ge 2$</span> and <span class="math-container">$a\ne b$</span>,
define subproblem <span class="math-container">$\mathcal S(a, b)$</span> as follows.
Let <span class="math-container">$S'_1, S'_2, \ldots, S'_{n-2}$</span> be obtained
from <span class="math-container">$S_1, \ldots, S_n$</span> by
removing the two sets <span class="math-container">$S_a$</span> and <span class="math-container">$S_b$</span>,
then replacing each remaining set <span class="math-container">$S$</span>
by <span class="math-container">$(S \setminus S_a) \cup \{n+1, n+2, \ldots, n+|S_a|-2\}$</span>.
(This removes all elements in <span class="math-container">$S_a$</span> from the problem,
and adds <span class="math-container">$|S_a|-2$</span> new elements to each remaining set.
Intuitively, this
forces <span class="math-container">$S_a$</span> to be chosen,
forces <span class="math-container">$S_b$</span> not to be chosen,
and artificially increases the size of any (non-empty)
union of the sets by <span class="math-container">$|S_a|-2$</span>.)
The subproblem is to determine whether
<span class="math-container">$\mathcal S(a, b)$</span> is feasible,
meaning that there exists <span class="math-container">$C'\subseteq [n-2]$</span>
such that
<span class="math-container">$$\textstyle|C'| \ge 1 + \big|\bigcup_{i\in C'} S'_i\big|.$$</span></p>
<p><strong>Lemma 1.</strong> <em>The original instance is feasible iff
at least one such subproblem <span class="math-container">$\mathcal S(a,b)$</span> is feasible.</em></p>
<p>(We leave as an exercise to verify
that the original instance is feasible iff,
for at least one such subproblem <span class="math-container">$\mathcal S(a, b)$</span>,
there exists <span class="math-container">$C'\subseteq [n-2]$</span> such that
<span class="math-container">$|C'|$</span> <em>equals</em> <span class="math-container">$1 + \big|\bigcup_{i\in C'}S'_i \big|.$</span>
Then, per Emil's comment,
relaxing the equality to a ``<span class="math-container">$\ge$</span>''
is okay because in the case that <span class="math-container">$|C'|$</span> is too large,
one can choose one set from <span class="math-container">$C'$</span> containing
each element of <span class="math-container">$\bigcup_{i\in C'} S'_i$</span>,
then choose additional, redundant sets from <span class="math-container">$C'$</span> as necessary
to achieve the correct size.)</p>
<p>By the lemma, it suffices to show that
each of the <span class="math-container">$O(n^2)$</span> subproblems is solvable in poly time.
The first proof below does this using linear programming
and randomized rounding.
The second proof does it using Hall's theorem.</p>
<hr />
<h5>First proof sketch (using randomized rounding)</h5>
<p>Consider the following linear-program relaxation of
<span class="math-container">$\mathcal S(a, b) = (S'_1, S'_2, \ldots, S'_{n'})$</span>,
with no objective function:</p>
<p><span class="math-container">$$\textsf{LP}(a, b) = {} \begin{cases}\begin{align}
\textstyle {\sum_{i=1}^{n'} x_i}
&amp; {} \ge 1 + \textstyle \big(\sum_{j=1}^{n'} y_j\big) \\
x_i &amp;{} \le y_j &amp;&amp; (i\in [n'], j \in S'_i) \\
0 \le x_i &amp;{} \le 1 &amp;&amp; (i\in [n']) \\
0 \le y_j &amp;{} \le 1 &amp;&amp; (j\in [n'])
\end{align}
\end{cases}
$$</span></p>
<hr />
<p>Here is the algorithm for solving <span class="math-container">$\mathcal S(a, b)$</span>:</p>
<ol>
<li>solve LP<span class="math-container">$(a, b)$</span> using any poly-time LP solver</li>
<li>if the LP admits a feasible solution: return 'yes'</li>
<li>else: return 'no'</li>
</ol>
<hr />
<p><em>Remark.</em> If a solution, rather than just a yes/no decision,
is required, one can adapt the rest of the proof to show that
from any feasible solution, a solution to the original problem
instance can be computed in poly time.  Or, more informatively,
that the basic feasible solutions (BFS) to the LP are 0/1,
so that by using a standard LP solver
that returns a BFS, a solution
to the original problem can be found in poly time.</p>
<hr />
<p>To finish we prove correctness of the algorithm.</p>
<p><strong>Claim 1.</strong> <em>If there is a solution
<span class="math-container">$(S'_{i_1}, \ldots, S'_{i_k})$</span> to <span class="math-container">$\mathcal S(a, b)$</span>,
then there is a corresponding feasible 0/1-solution <span class="math-container">$(x,y)$</span>
to LP<span class="math-container">$(a, b)$</span>.</em></p>
<p>(Indeed, let <span class="math-container">$C'= \{i_1, i_2, \ldots, i_k\}$</span>.
Take <span class="math-container">$x_i = 1$</span> if <span class="math-container">$i\in C'$</span>
and <span class="math-container">$y_j = 1$</span>
if <span class="math-container">$j\in \bigcup_{i\in C'} S'_i$</span>.)</p>
<p>From Claim 1, it follows that if the algorithm returns 'no',
then <span class="math-container">$\mathcal S(a, b)$</span> has no solution, so the algorithm
is correct in this case.
To finish, we prove the following claim,
which implies that the algorithm is also correct
in the case that it returns 'yes'.</p>
<hr />
<p><strong>Claim 2.</strong> <em>If LP<span class="math-container">$(a, b)$</span> is feasible,
then <span class="math-container">$\mathcal S(a, b)$</span> has a solution.</em></p>
<p>To prove it, consider the following randomized rounding scheme:</p>
<ol>
<li>let <span class="math-container">$(x, y)$</span> be a feasible solution to LP<span class="math-container">$(a, b)$</span></li>
<li>choose a value <span class="math-container">$\lambda\in (0,1]$</span> uniformly at random</li>
<li>let r.v. <span class="math-container">$C = \{i : \lambda \le x_i\}$</span></li>
<li>let r.v. <span class="math-container">$U = \{j : \lambda \le y_j\}$</span></li>
</ol>
<hr />
<p>Note that
<span class="math-container">$i \in C \wedge j \in S'_i
\implies \lambda \le x_i \wedge x_i \le y_j
\implies \lambda \le y_j
\implies j \in U$</span>.</p>
<p>It follows that <span class="math-container">$\bigcup_{i\in C} S'_i \subseteq U$</span>.</p>
<p>On the other hand, the expected sizes of <span class="math-container">$C$</span> and <span class="math-container">$U$</span>
are related (via the LP constraints) as follows
<span class="math-container">$$\textstyle E[|C|] = \sum_{i=1}^{n'} x_i
\ge 1 + \big(\sum_{j=1}^{n'} y_j\big)
= 1 + E[|U|].$$</span></p>
<p>Since <span class="math-container">$E[|C| - |U|] \ge 1$</span>,
there is an outcome of the experiment in which
<span class="math-container">$$\textstyle |C| \ge 1 + |U| \ge 1 + |\bigcup_{i\in C} S_i|,$$</span> as desired.
<span class="math-container">$~~~\Box$</span></p>
<hr />
<h5>Second proof sketch (using Hall's theorem)</h5>
<p>Fix a subproblem instance
<span class="math-container">$\mathcal S(a, b)=(S'_1, S'_2, \ldots, S'_{n'})$</span>.
Recall that the goal is to determine whether
there exists <span class="math-container">$C\subseteq [n']$</span>
such that
<span class="math-container">$$\textstyle|C| \ge 1 + \big|\bigcup_{i\in C} S'_i\big|.$$</span></p>
<p>The instance is <em>infeasible</em> if and only if,
for all <span class="math-container">$C\subseteq [n']$</span>,
<span class="math-container">$$\textstyle|C| \le |\bigcup_{i\in C} S'_i|.$$</span>
By <a href="https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem" rel="nofollow noreferrer">Hall's theorem</a>,
this condition holds for all <span class="math-container">$C$</span> if and only
<span class="math-container">$\mathcal S(a, b)$</span> has a <em>transversal</em>,
meaning a matching that
assigns each set <span class="math-container">$S'_i$</span> a distinct element <span class="math-container">$j\in S'_i$</span>
(so that no element is assigned to more than one set).
Thus, infeasibility can be determined
by solving the bipartite-matching problem
in the bipartite graph representing the set system <span class="math-container">$\mathcal S(a, b)$</span>.</p>
<p>Bipartite matching is solvable in polynomial time,
so we are done.
(If there is no such matching,
existing poly-time algorithms
prove it by returning a dual solution,
in the form of a set <span class="math-container">$C$</span> such that
<span class="math-container">$\textstyle|C| &gt; |\bigcup_{i\in C} S'_i|.$</span>
This then gives a solution to <span class="math-container">$\mathcal S(a, b)$</span>.)
<span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2024-03-12T08:00:08.950Z
Nice. I thought of using LP, but didn’t have enough determination to actually figure it out. Note that the last part can be alternatively proved using the argument I gave above in the comments: once $|C|\ge|\bigcup_{i\in C}S_i|$, pick $i_x\in C$ such that $x\in S_{i_x}$ for each $x\in U':=\bigcup_{i\in C}$, and let $\{i_x:x\in U'\}\subseteq C'\subseteq C$ be such that $|C'|=|U'|$.
Emil Jeřábek
CC BY-SA 4.0
2024-03-14T15:28:22.730Z
Thanks @EmilJeřábek, I incorporated your argument (now in the proof of Lemma 1).
Neal Young
CC BY-SA 4.0
2024-03-14T17:04:33.920Z
My intuition was incorrect, that is why I hedged a bit. @NealYoung glad that you didn't get swayed and found the algorithm.
Chandra Chekuri
CC BY-SA 4.0
2024-03-12T03:08:07.053Z
2024-03-12T16:21:33.163Z
2024-03-12T16:21:33.163Z
Neal Young
<p>Given n sets <span class="math-container">$S_1,...,S_n$</span> such that <span class="math-container">$S_i \subset \{1,...,n\}$</span> is there a poly(n) algorithm to find <span class="math-container">$1 \leq i_1 &lt; i_2 &lt;.... &lt; i_k \leq n$</span> such that <span class="math-container">$|\bigcup_{j=1}^k S_{i_j} | = k$</span> where <span class="math-container">$1 \leq k &lt; n$</span>. Any help would be appreciated.</p>

CC BY-SA 4.0
2024-03-06T21:19:01.943Z
It appears that the problem is NP-Complete via a reduction for Exact-3-Cover (with some modifications). It may be worth trying.
Chandra Chekuri
CC BY-SA 4.0
2024-03-11T09:50:45.177Z
@ChandraChekuri, I can't see how to use Exact-3-Cover to show that the problem is NP-Hard. If possible, can you expand on your comment?
Rishabh Kothary
CC BY-SA 4.0
2024-03-11T09:51:14.410Z
@NealYoung I didn't mean to allow $k=0$ edge case. I modified the question.
Rishabh Kothary
CC BY-SA 4.0
2024-03-11T09:59:25.450Z
Put $k=|\bigcup_iS_i|$, and for each $x\in\bigcup_iS_i$, pick one $S_i$ that contains it. If this results in less than $k$ sets, add any of the remaining ones to make it right.
Emil Jeřábek
CC BY-SA 4.0
2024-03-11T10:07:51.030Z
@EmilJeřábek, there was a typo k < n in the question, which I edited. Your algorithm will fail for k = n.
Rishabh Kothary
CC BY-SA 4.0
2024-03-11T17:26:59.870Z
RIshabh see [the posting guidelines](https://cstheory.stackexchange.com/help/how-to-ask).  They suggest including background info such as where the problem arises, what you know about it, what you've tried...
Neal Young
CC BY-SA 4.0
2024-03-11T17:34:19.150Z
I think I prefer the following formulation: Given a bipartite graph $E\subseteq[n]\times[n]$, find $\varnothing\ne X\subsetneq[n]$ such that $|X|=|E(X)|$ (or: $|X|\ge|E(X)|$) if it exists.
Emil Jeřábek
CC BY-SA 4.0
2024-03-11T18:51:10.927Z
Yes, I meant neighbours. For the $|X|=|N(X)|$ version, $N(X)$ is nonempty because $X$ is, but you are right that in the $|X|\ge|N(X)|$ version, I should demand $N(X)\ne\varnothing$ rather than $X\ne\varnothing$.
Emil Jeřábek
<ds.algorithms><co.combinatorics><randomized-algorithms>
A question on combinatorial algorithm
Rishabh Kothary
# A question on combinatorial algorithm

(Asked by: username_0 on 2024-03-06)

Given n sets $S\_1,...,S\_n$ such that $S\_i \subset \{1,...,n\}$ is there a poly(n) algorithm to find $1 \leq i\_1 < i\_2 <.... < i\_k \leq n$ such that $|\bigcup\_{j=1}^k S\_{i\_j} | = k$ where $1 \leq k < n$. Any help would be appreciated.

**Tags:** ds.algorithms, co.combinatorics, randomized-algorithms
> **Comments:**
> **username_1**: It appears that the problem is NP-Complete via a reduction for Exact-3-Cover (with some modifications). It may be worth trying.  
> **username_0**: @ChandraChekuri, I can't see how to use Exact-3-Cover to show that the problem is NP-Hard. If possible, can you expand on your comment?  
> **username_0**: @NealYoung I didn't mean to allow $k=0$ edge case. I modified the question.  
> **username_2**: Put $k=|\bigcup_iS_i|$, and for each $x\in\bigcup_iS_i$, pick one $S_i$ that contains it. If this results in less than $k$ sets, add any of the remaining ones to make it right.  
> **username_0**: @EmilJeřábek, there was a typo k < n in the question, which I edited. Your algorithm will fail for k = n.  
> **username_3**: RIshabh see [the posting guidelines](https://cstheory.stackexchange.com/help/how-to-ask).  They suggest including background info such as where the problem arises, what you know about it, what you've tried...  
> **username_2**: I think I prefer the following formulation: Given a bipartite graph $E\subseteq[n]\times[n]$, find $\varnothing\ne X\subsetneq[n]$ such that $|X|=|E(X)|$ (or: $|X|\ge|E(X)|$) if it exists.  
> **username_2**: Yes, I meant neighbours. For the $|X|=|N(X)|$ version, $N(X)$ is nonempty because $X$ is, but you are right that in the $|X|\ge|N(X)|$ version, I should demand $N(X)\ne\varnothing$ rather than $X\ne\varnothing$.  

---

## 1 answers

### Answer by username_3 on 2024-03-12. Score: 6 | Accepted answer

[*EDIT*: Added second proof, using Hall's theorem.]

---

**Theorem 1.** *There is a poly-time algorithm for the problem.*

We give a direct proof, then another proof using [Hall's theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem).

Both proofs use the following utility lemma,
which recasts the problem into a more convenient form.

Fix a problem instance $(S\_1, S\_2, \ldots, S\_n)$.
The problem is to decide
whether the instance is *feasible*,
meaning that there exists $C\subseteq [n]$
such that $n-1 \ge |C| = |\bigcup\_{i\in C} S\_i| \ge 1$.

If there is a set $S\_i$ of size 1, the instance is feasible
(take $C=\{i\}$), so assume otherwise.
Note that in the definition above
WLOG we can restrict to collections $C$
containing at least one index $a$ with $|S\_a| \ge 2$,
and *not* containing at least one other index $b\in[n]$.

Given $(a,b)\in [n]\times [n]$ with $|S\_a| \ge 2$ and $a\ne b$,
define subproblem $\mathcal S(a, b)$ as follows.
Let $S'\_1, S'\_2, \ldots, S'\_{n-2}$ be obtained
from $S\_1, \ldots, S\_n$ by
removing the two sets $S\_a$ and $S\_b$,
then replacing each remaining set $S$
by $(S \setminus S\_a) \cup \{n+1, n+2, \ldots, n+|S\_a|-2\}$.
(This removes all elements in $S\_a$ from the problem,
and adds $|S\_a|-2$ new elements to each remaining set.
Intuitively, this
forces $S\_a$ to be chosen,
forces $S\_b$ not to be chosen,
and artificially increases the size of any (non-empty)
union of the sets by $|S\_a|-2$.)
The subproblem is to determine whether
$\mathcal S(a, b)$ is feasible,
meaning that there exists $C'\subseteq [n-2]$
such that
$$\textstyle|C'| \ge 1 + \big|\bigcup\_{i\in C'} S'\_i\big|.$$

**Lemma 1.** *The original instance is feasible iff
at least one such subproblem $\mathcal S(a,b)$ is feasible.*

(We leave as an exercise to verify
that the original instance is feasible iff,
for at least one such subproblem $\mathcal S(a, b)$,
there exists $C'\subseteq [n-2]$ such that
$|C'|$ *equals* $1 + \big|\bigcup\_{i\in C'}S'\_i \big|.$
Then, per Emil's comment,
relaxing the equality to a ``$\ge$''
is okay because in the case that $|C'|$ is too large,
one can choose one set from $C'$ containing
each element of $\bigcup\_{i\in C'} S'\_i$,
then choose additional, redundant sets from $C'$ as necessary
to achieve the correct size.)

By the lemma, it suffices to show that
each of the $O(n^2)$ subproblems is solvable in poly time.
The first proof below does this using linear programming
and randomized rounding.
The second proof does it using Hall's theorem.

---

##### First proof sketch (using randomized rounding)

Consider the following linear-program relaxation of
$\mathcal S(a, b) = (S'\_1, S'\_2, \ldots, S'\_{n'})$,
with no objective function:

$$\textsf{LP}(a, b) = {} \begin{cases}\begin{align}
\textstyle {\sum\_{i=1}^{n'} x\_i}
& {} \ge 1 + \textstyle \big(\sum\_{j=1}^{n'} y\_j\big) \\
x\_i &{} \le y\_j && (i\in [n'], j \in S'\_i) \\
0 \le x\_i &{} \le 1 && (i\in [n']) \\
0 \le y\_j &{} \le 1 && (j\in [n'])
\end{align}
\end{cases}
$$

---

Here is the algorithm for solving $\mathcal S(a, b)$:

1. solve LP$(a, b)$ using any poly-time LP solver
2. if the LP admits a feasible solution: return 'yes'
3. else: return 'no'

---

*Remark.* If a solution, rather than just a yes/no decision,
is required, one can adapt the rest of the proof to show that
from any feasible solution, a solution to the original problem
instance can be computed in poly time. Or, more informatively,
that the basic feasible solutions (BFS) to the LP are 0/1,
so that by using a standard LP solver
that returns a BFS, a solution
to the original problem can be found in poly time.

---

To finish we prove correctness of the algorithm.

**Claim 1.** *If there is a solution
$(S'\_{i\_1}, \ldots, S'\_{i\_k})$ to $\mathcal S(a, b)$,
then there is a corresponding feasible 0/1-solution $(x,y)$
to LP$(a, b)$.*

(Indeed, let $C'= \{i\_1, i\_2, \ldots, i\_k\}$.
Take $x\_i = 1$ if $i\in C'$
and $y\_j = 1$
if $j\in \bigcup\_{i\in C'} S'\_i$.)

From Claim 1, it follows that if the algorithm returns 'no',
then $\mathcal S(a, b)$ has no solution, so the algorithm
is correct in this case.
To finish, we prove the following claim,
which implies that the algorithm is also correct
in the case that it returns 'yes'.

---

**Claim 2.** *If LP$(a, b)$ is feasible,
then $\mathcal S(a, b)$ has a solution.*

To prove it, consider the following randomized rounding scheme:

1. let $(x, y)$ be a feasible solution to LP$(a, b)$
2. choose a value $\lambda\in (0,1]$ uniformly at random
3. let r.v. $C = \{i : \lambda \le x\_i\}$
4. let r.v. $U = \{j : \lambda \le y\_j\}$

---

Note that
$i \in C \wedge j \in S'\_i
\implies \lambda \le x\_i \wedge x\_i \le y\_j
\implies \lambda \le y\_j
\implies j \in U$.

It follows that $\bigcup\_{i\in C} S'\_i \subseteq U$.

On the other hand, the expected sizes of $C$ and $U$
are related (via the LP constraints) as follows
$$\textstyle E[|C|] = \sum\_{i=1}^{n'} x\_i
\ge 1 + \big(\sum\_{j=1}^{n'} y\_j\big)
= 1 + E[|U|].$$

Since $E[|C| - |U|] \ge 1$,
there is an outcome of the experiment in which
$$\textstyle |C| \ge 1 + |U| \ge 1 + |\bigcup\_{i\in C} S\_i|,$$ as desired.
$~~~\Box$

---

##### Second proof sketch (using Hall's theorem)

Fix a subproblem instance
$\mathcal S(a, b)=(S'\_1, S'\_2, \ldots, S'\_{n'})$.
Recall that the goal is to determine whether
there exists $C\subseteq [n']$
such that
$$\textstyle|C| \ge 1 + \big|\bigcup\_{i\in C} S'\_i\big|.$$

The instance is *infeasible* if and only if,
for all $C\subseteq [n']$,
$$\textstyle|C| \le |\bigcup\_{i\in C} S'\_i|.$$
By [Hall's theorem](https://en.wikipedia.org/wiki/Hall%27s_marriage_theorem),
this condition holds for all $C$ if and only
$\mathcal S(a, b)$ has a *transversal*,
meaning a matching that
assigns each set $S'\_i$ a distinct element $j\in S'\_i$
(so that no element is assigned to more than one set).
Thus, infeasibility can be determined
by solving the bipartite-matching problem
in the bipartite graph representing the set system $\mathcal S(a, b)$.

Bipartite matching is solvable in polynomial time,
so we are done.
(If there is no such matching,
existing poly-time algorithms
prove it by returning a dual solution,
in the form of a set $C$ such that
$\textstyle|C| > |\bigcup\_{i\in C} S'\_i|.$
This then gives a solution to $\mathcal S(a, b)$.)
$~~~~\Box$

> **Comments:**
> **username_2**: Nice. I thought of using LP, but didn’t have enough determination to actually figure it out. Note that the last part can be alternatively proved using the argument I gave above in the comments: once $|C|\ge|\bigcup_{i\in C}S_i|$, pick $i_x\in C$ such that $x\in S_{i_x}$ for each $x\in U':=\bigcup_{i\in C}$, and let $\{i_x:x\in U'\}\subseteq C'\subseteq C$ be such that $|C'|=|U'|$.  
> **username_3**: Thanks @EmilJeřábek, I incorporated your argument (now in the proof of Lemma 1).  
> **username_1**: My intuition was incorrect, that is why I hedged a bit. @NealYoung glad that you didn't get swayed and found the algorithm.  

---

