Can I find the subsets of a domain given two sets

Quote:

Originally Posted by rajetta

Hi,
I've two sets, X and Y. Sample data is in this shared PDF:
https://docs.google.com/fileview?id=...MTYxMjU4&hl=en
I want to divide the set X (or Y) so that I can get Set X1(A,B) and Set X2(C,D). Is it possible to do this mathematically (If yes, I'll try to code in Software which is my ultimate goal).
I may want to divide it 'n' times (instead of 2, as in example) so that I can deal with manageable data.

For those who are interested, I'll be applying Hungarian Matching algorithm on the divided sets. As of now, the data is huge and even optimal implementations take huge amount of memory (which we don't have).

Thanks

From what I understand, you have a weighted bipartite graph and you want to divide it into smaller subgraphs, as part of an overall divide-and-conquer strategy.

This is only possible if the data looks like your diagram, where there are no edges between {A,B} and {5,6,7,8} or between {C,D} and {1,2,3,4}. For a general bipartite graph this may not be the case.

I don't know if there's a commonly used term, but let's say you're looking for "isolatable" sub-graphs.

A naive algorithm comes to mind, which would be very slow for large graphs. Check a given pair in set X, say S1 = {A, B}. Consider the set S2 of all vertices in Y connected by edges to {A, B}. If S2 = Y, move on to another pair. Otherwise we know S2 is a proper subset of Y. Now check the set S3 = X - S1 and start building up a set S4 of all vertices in Y connected by edges to S3. If you find any element of S4 belonging to S2, move on to another pair. Otherwise, if you find that S2 intersect S4 is the empty set, then you've found your isolatable subgraph. Iterate all 2-subsets of X, then all 3-subsets of X, etc. If you start from 2-subsets and work upwards, you will not need to recursively look for subgraphs in your subgraphs, because they will already be as small as possible. You can stop checking k-subsets when k exceeds half the order of X.

In practice you'd want to be using boolean arrays, rather than building up new lists and using some sort of contains() function.

Depending on your needs, this naive method might be good enough?

I've never worked on an assignment problem algorithm before, so I'm not sure what other approaches you might consider besides your proposed divide-and-conquer.

(Made some small edits.)