How to match a set against a set of sets, completely

Question

This problem is similar to the "Exact Hitting Set" problem (http://en.wikipedia.org/wiki/Exact_cover#Exact_hitting_set) but with slightly different constraints.

I am looking for libraries, implementations, or papers that solve the following.

Say I have a set of sets S, and is initialized as follows:

S = {N, O, P, E};

N = {1, 2, 5}
O = {4, 5}
P = {1, 6, 7}
E = {2, 3, 8}};

S has n sets, and each subset set is of unknown size. In this example n = 4

Now I have another set X of size n, which is initialized to:

X = {1, 2, 4, 6}

What I need to do, is match each element in X to one and only one set in S.

So S should be completely satisfied with all of it's sets mapped to X and vice versa.

X[0] --> N
X[1] --> E
X[2] --> O
X[3] --> P

The main problem I am having is how to deal with the duplicated data with in the sets of S. How do I deal with these collisions? And How to implement the algorithm in such a way that is relatively scalable?

If you have any information that could point me in the right direction to solve this will be very much appreciated.

Answer 1

You could create a bipartite graph in the following manner:

• For each element in the set X create a node in the U disjoint set of the graph
• For each subset in the set S create a node in the V disjoint set of the graph
• If element of X in subset of S then create an edge between the corresponding nodes in U and V

Then having the bipartite graph you can solve the problem using hopcroft karp algorithm to produce the maximum cardinality matching.(O(|E|sqrt(V)))