# Set partitioning algorithm

I'm a working software engineer and I'm trying to develop some planning software. I have faced the following problem.

I have some finite set $U$ of some distinct elements $e_i \in U$.

I have some subsets $A_i \subset U$, where $i \in \{1, 2, \cdots, N\}$.

I have an array of integers $<k_1, k_2, \cdots, k_N >$. Each integer $k_i \leq |A_i|$ and $$\sum_{i \in \{1, 2, \cdots, N\}} k_i \leq | \cup_{i \in \{1, 2, \cdots, N\}} A_i |$$.

I want to find sets $B_i$, where $i \in \{1, 2, \cdots, N\}$, such that $|B_i| = k_i$ and $$\forall i \in \{1, 2, \cdots, N\} . B_i \subset A_i$$ and $$\forall i, j \in \{1, 2, \cdots, N\} . B_i \cap B_j = \emptyset$$

The choice of actual $B_i$ doesn't matter at all.

1. I'd like to find is it possible at all. It seems to me that it is, since it's obviously possible for not intersecting $A_i$, and if they intersects we can reduce the problem to not intersecting $A'_i$

2. I'd like to find fast algorithm that will not-deterministically choose any $B_i$. I'd like to find the complexity of the problem. It seems that there should be some fast algorithm and problem doesn't seem similar to NP-hard problems, but I somehow feel that it can be NP-hard.

The actual environment is that there are around 50 000 000 elements in $U$ and N is around 100.

Is it some known problem? Where can I read on the matter? Is there any fast algorithm? What is the best way to perform such partitioning in given environment.

• If I understand correctly, when each $k_i$ is equal to $1$, then this is equivalent to finding a system of distinct representatives (also known as a transversal). I'm not sure what happens when $k_i \neq 1$. – mhum Nov 8 '11 at 15:54
• Victor: It is not always possible. For example, consider the case where N=3, k1=k2=k3=1, A1=A2={1}, A3={2,3}. – Tsuyoshi Ito Nov 8 '11 at 15:58
• You will at least need to strengthen the constraints on the $k_i$ to sums and unions over arbitrary subsets of $\{1,\dots,N\}$. I think it's a simple induction over $N$ to show that this suffices, don't really have time to work it out now, though. – Klaus Draeger Nov 9 '11 at 13:48

The problem can be solved via the assignment problem/network flow. Create a bipartite graph with the left side consisting of $N$ vertices $a_1,\ldots,a_N$ corresponding to the sets $A_1,\ldots,A_n$. The right side has $m$ vertices $u_1,\ldots,u_m$ one for each element in $U$. Connect $a_i$ via directed arcs of capacity $1$ to each element vertex that $A_i$ contains. Now add a source vertex $s$ and connect it via an arc of capacity $k_i$ to $a_i$. Connect each $u_j$ to a sink vertex $t$ with an arc capacity of $1$. The problem has a solution if and only if there is an $s$-$f$ flow of value $\sum_i k_i$ in this network. An integral flow would give you a desired solution.