Set partitioning algorithm

Question

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.

Answer 1

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.