I am not sure whether the following problem has been studied. Any help would be greatly appreciated. I have $L$ sets, $S_1, S_2,...,S_L$, each of $n$ elements, taken from a universe of $N$ elements. My aim is to find subsets $S'_1 \subseteq S_1, S'_2 \subseteq S_2,...,S'_{M} \subseteq S_M$ of $k$ elements each, such that the subsets are pair-wise disjoint and the number of subsets is maximal.

As an example, consider the three sets ${S_1} = \left\{ {1,2,3,4} \right\},{S_2} = \left\{ {2,3,5,6} \right\},{S_3} = \left\{ {1,3,6,7} \right\}$ where $n=4$ and $k=2$. Then an optimal solution is 3 sets: $S'_1 = \left\{ {1,2} \right\},S'_2 = \left\{ {3,5} \right\},S'_3 = \left\{ {6,7} \right\}$.

The problem above is hard in general. However, it turns out that when the maximum pair-wise intersection is $2(n-k)/(L-1)$, a solution of $L$ subsets is guaranteed to exist. Assume that the maximum pair-wise intersection is $2(n-k)/(L-1)$, and that no element appears more than twice in the sets $S_1, S_2,...,S_L$. Denote by $\tilde S_i$ the elements in $S_i$ that belong to $S_i$ only (i.e., not shared by any other set). Then we can represent the problem as a complete graph with $L$ nodes, where an edge between edge $i$ and edge $j$ is of weight $|S_{ij}|$ units.

The problem: How can we distribute the weights between the nodes such that node $i$ receives $k-|\tilde S_i|$ units (if $|\tilde S_i| < k$) out of the weights on edges connected to node $i$ (i.e., together with the elements in $\tilde S_i$ it has $k$ elements)?.

In other words, we want to distribute non-negative integer edge weights between nodes such that each node receives at least $k$ units. It can be shown easily that if node $i$ receives $1/2$ of each weight on its connected edges, then the node will have at least $k$ units. However, the weights are not necessarily even, so this "solution" cannot be applied in general.



Your Answer

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