<p>@Chandra Chekuri's comment made me think about casting the problem as a maximum flow problem (solvable in polynomial time):</p>

<ul>
<li><span class="math-container">$\forall i$</span>, have a  vertex <span class="math-container">$v_{i}$</span>, connected to the source by an edge with capacity <span class="math-container">$b_i$</span>.</li>
<li><span class="math-container">$\forall i$</span>, <span class="math-container">$ \forall e \in S_i$</span>, have a vertex <span class="math-container">$v_{e}$</span>, connected to all <span class="math-container">$v_j$</span> such that <span class="math-container">$e \in S_j$</span> with capacity <span class="math-container">$1$</span>, and connected to the sink with capacity <span class="math-container">$1$</span>.</li>
</ul>

CC BY-SA 4.0
2020-05-25T21:55:08.490Z
2020-05-25T21:55:08.490Z
Stephane Bersier
<p>Create a bipartite graph:</p>

<ul>
<li>For every element <span class="math-container">$x\in\bigcup_{i=1}^nS_i$</span>, introduce a corresponding vertex <span class="math-container">$u(x)$</span>.</li>
<li>For every set <span class="math-container">$S_i$</span>, introduce a corresponding vertex <span class="math-container">$v(S_i)$</span>.</li>
<li>Connect vertex <span class="math-container">$u(x)$</span> to vertex <span class="math-container">$v(S_i)$</span> by an edge, if and only if <span class="math-container">$x\in S_i$</span>.</li>
</ul>

<p>Then your problem essentially asks, whether there exists a subset <span class="math-container">$F$</span> of the edges, so that</p>

<ul>
<li>every vertex <span class="math-container">$u(x)$</span> is incident to at most one edge in <span class="math-container">$F$</span>, and</li>
<li>every vertex <span class="math-container">$v(S_i)$</span> is incident to at least <span class="math-container">$b_i$</span> edges in <span class="math-container">$F$</span>.</li>
</ul>

<p>This is an instance of the so-called <span class="math-container">$f$</span>-factor problem, and hence solvable in polynomial time.
See for instance the book <em>"Matching Theory"</em> by László Lovász and Michael D. Plummer.</p>

CC BY-SA 4.0
2020-05-25T20:44:31.103Z
Perhaps it is easier to see this via network flow that generalizes bipartite matching  problems. Matching Theory book is rather old and hard to find. See Kleinberg-Tardos book or Jeff Erickson's  notes on network flow and applications. https://jeffe.cs.illinois.edu/teaching/algorithms/
Chandra Chekuri
CC BY-SA 4.0
2020-05-25T20:19:31.853Z
2020-05-25T20:19:31.853Z
Gamow
<p>Is the decision problem below NP-complete?</p>

<p>Given sets <span class="math-container">$S_1, ... , S_n$</span>, as well as bounds <span class="math-container">$b_1, ... , b_n$</span>, is it possible to pick pairwise disjoint subsets <span class="math-container">$U_1, ... , U_n$</span> such that <span class="math-container">$U_i \subset S_i$</span> and <span class="math-container">$|U_i| \geqslant b_i$</span> for all <span class="math-container">$i$</span>?</p>

<cc.complexity-theory><np-complete>
Disjoint subsets problem complexity
Stephane Bersier
# Disjoint subsets problem complexity

(Asked by: username_0 on 2020-05-25)

Is the decision problem below NP-complete?

Given sets $S\_1, ... , S\_n$, as well as bounds $b\_1, ... , b\_n$, is it possible to pick pairwise disjoint subsets $U\_1, ... , U\_n$ such that $U\_i \subset S\_i$ and $|U\_i| \geqslant b\_i$ for all $i$?

**Tags:** cc.complexity-theory, np-complete

---

## 2 answers

### Answer by username_0 on 2020-05-25. Score: 3 | Accepted answer

@Chandra Chekuri's comment made me think about casting the problem as a maximum flow problem (solvable in polynomial time):

* $\forall i$, have a vertex $v\_{i}$, connected to the source by an edge with capacity $b\_i$.
* $\forall i$, $ \forall e \in S\_i$, have a vertex $v\_{e}$, connected to all $v\_j$ such that $e \in S\_j$ with capacity $1$, and connected to the sink with capacity $1$.


---

### Answer by username_1 on 2020-05-25. Score: 4

Create a bipartite graph:

* For every element $x\in\bigcup\_{i=1}^nS\_i$, introduce a corresponding vertex $u(x)$.
* For every set $S\_i$, introduce a corresponding vertex $v(S\_i)$.
* Connect vertex $u(x)$ to vertex $v(S\_i)$ by an edge, if and only if $x\in S\_i$.

Then your problem essentially asks, whether there exists a subset $F$ of the edges, so that

* every vertex $u(x)$ is incident to at most one edge in $F$, and
* every vertex $v(S\_i)$ is incident to at least $b\_i$ edges in $F$.

This is an instance of the so-called $f$-factor problem, and hence solvable in polynomial time.
See for instance the book *"Matching Theory"* by László Lovász and Michael D. Plummer.

> **Comments:**
> **username_2**: Perhaps it is easier to see this via network flow that generalizes bipartite matching  problems. Matching Theory book is rather old and hard to find. See Kleinberg-Tardos book or Jeff Erickson's  notes on network flow and applications. https://jeffe.cs.illinois.edu/teaching/algorithms/  

---

