4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – mhum
    Nov 8, 2011 at 15:54
  • $\begingroup$ Victor: It is not always possible. For example, consider the case where N=3, k1=k2=k3=1, A1=A2={1}, A3={2,3}. $\endgroup$ Nov 8, 2011 at 15:58
  • $\begingroup$ 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. $\endgroup$ Nov 9, 2011 at 13:48

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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