6
$\begingroup$

The input: Given a set $U=\{1, \ldots, k\}$ called the universe. Let $C=\{S_1, \ldots, S_n\}$ be a collection of subsets of $U$ and let $ s_j$ be a nonnegative integer for all $j=1,\ldots,n$ such that $\sum_{j=1}^{n} s_j=k$.

The question: Are there $n$ subsets $A_j$ of $S_j$ (i.e., $A_j\subset S_j$) such that

$$ \quad\bigcup\limits_{j=1}^{n}A_j=U,\\ \quad \quad\;\;\;\,\;\;\,A_j \cap A_i = \emptyset, i\neq j,\\ |A_j|=s_j. $$

Is this problem NP-hard?

I was trying to reduce PARTITION to this problem by setting $n=2$ and $k$ an even number and $s_j=k/2$ but the constraints $|A_j|=k/2$ do not help me.

$\endgroup$
7
$\begingroup$

When $s_j = 1$ for all $j$, the problem is the same as deciding whether a bipartite graph has a perfect matching. In the general case, we can solve it using maximum flow.

Set up a flow network with the following components:

  • A source $s$, a sink $t$, a vertex $S_j$ for each set, and a vertex $x_i$ for each element in the universe.

  • Connect $s$ to each $S_j$ with an edge of capacity $s_j$.

  • For each $x_i \in S_j$, connect $S_j$ to $x_i$ with an infinite capacity edge.

  • Connect each $x_i$ to $t$ with an edge of capacity $1$.

Now compute the maximum flow. If it equals $|U|$ then the instance has a solution. Moreover, you can extract the solution from a maximum integer flow.

The max flow min cut theorem also gives us a Hall-like criterion: a solution exists if for every set $X$ of elements, $$ \sum_{j\colon S_j \cap X \neq \emptyset} s_j \geq |X|. $$ That is, if we sum the "capacities" $s_j$ for all sets $S_j$ that intersect $X$, then we need to get at least $|X|$. This is clearly a necessary condition, and the max flow min cut theorem shows that it is sufficient.

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