CODEWITHSUNDEEP
algorithmset
Torgny
Torgny

Reputation: 279

Subset of mutually exclusive items from sets

I have sets S_0, ..., S_N. How do I find the largest subset T, such that the intersection I_i of T and S_i (for each 0 <= i <= N) contains at most one element.

I have a solution for this, but I'm guessing that it's unnecessarily slow (essentially several nested for-loops trying out all combinations). So my question is:

Upvotes: 2

Views: 1212

Answers (2)

Peter de Rivaz
Peter de Rivaz

Reputation: 33509

I think you are unlikely to find an efficient general algorithm for this problem because I believe it is NP complete.

If you had an efficient algorithm to solve this, then you could solve the maximum independent set problem.

Sketch of Proof

Suppose you have a graph, then for each edge construct a set containing {i,j} where i and j are the vertices connected by the edge.

Then the largest subset T for these sets will be the maximal independent set for your graph.

Conversion to Maximal independent set

More usefully, you can also express your problem in terms of finding a maximal independent set for the graph where there is an edge between a and b if and only if there is a set that contains both a and b.

You may then be able to use some standard solvers for the maximal independent set problem such as the one in Pythons NetworkX.

Upvotes: 3

Dan D.
Dan D.

Reputation: 74675

You could speed up your program by caching whether the intersection of sets S_a and S_b are empty or not. Rather than building the set T which I think is the union of some of the sets in S. You keep a list T of the indexes of sets and to check if a set S_n intersects with T you check if in the table for the set in T that S_n intersects with one of them.

I did this in one of my Python programs as the set intersection test was the slow spot.

Upvotes: 0

Related Questions