1
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 4
    $\begingroup$ 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 $\endgroup$ – Chandra Chekuri May 25 at 20:44
3
$\begingroup$

@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$.
| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.