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$?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
Create a bipartite graph:
Then your problem essentially asks, whether there exists a subset $F$ of the edges, so that
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.
@Chandra Chekuri's comment made me think about casting the problem as a maximum flow problem (solvable in polynomial time):