snippetMinor
How to partition a set into disjoints subsets each of given size?
Viewed 0 times
partitioneachintosizesubsetshowgivensetdisjoints
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#66198, answer score: 7
Revisions (0)
No revisions yet.