1
$\begingroup$

I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S. The cardinality of each of these sets can be anywhere from 1 to N. The number of sets is variable, but is necessarily at least N.

e.g.

$S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$

Sets:

$\{3, 6\}$ $\{1, 2, 5\}$ $\{5\}$ $\{2, 6\}$ $\{2, 5\}$ $\{7, 8\}$ $\{1, 3, 5\}$ $\{7, 9\}$ $\{4, 8, 9\}$ $\{4, 5\}$

I'm looking for an algorithm that will let me determine if there is a group of N sets, where each element of S is contained in a different set (the other elements in the set are irrelevant). Note that every element of S will always be represented at least once in the collection of sets (otherwise it is obvious that no solution is possible).

For this example, a possible solution is:

$\{\mathbf{1}, 2, 5\}$ $\{\mathbf{2}, 5\}$ $\{1, \mathbf{3}, 5\}$ $\{\mathbf{4}, 5\}$ $\{\mathbf{5}\}$ $\{2, \mathbf{6}\}$ $\{\mathbf{7}, 9\}$ $\{7, \mathbf{8}\}$ $\{4, 8, \mathbf{9}\}$

(bold numbers indicate the element of S for which each set was selected)

But if we were to exclude the set $\{4, 5\}$ from the pool of available sets, there would be no possible solution, despite every number being represented at least once in the available sets, and the number of sets still being at least N.

My N will not be more than 100, and the number of sets could be up to 100,000. The frequency of numbers in the sets will likely be very unevenly distributed, so, for example, there might be 95% of the sets that contain a 1, but only <1% of sets that contain a 3.

Obviously the best performance is desirable, but I would appreciate any algorithm that is better than a brute-force search of every possible combination of sets.

$\endgroup$
2
$\begingroup$

You are looking for a perfect matching. Consider the bipartite graph in which the left side consists of $N$ vertices corresponding to the numbers in $S$, and the right side contains a vertex for each set. Connect $x$ on the left to $y$ on the right if $x \in y$. Your problem is solvable if there is a matching that matches all of the left side. This is the classical problem of unweighted maximum matching in bipartite graphs, which has many efficient algorithms.

$\endgroup$

Your Answer

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

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