# Disjoint subsets problem complexity

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

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.

• 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. jeffe.cs.illinois.edu/teaching/algorithms – Chandra Chekuri May 25 '20 at 20:44

@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$$.