1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.