Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find if any set is covered by member sets

Tags:

algorithm

set

[Please let me know if this maps to a known problem]

I have n sets of varying sizes. Each element in a set is unique. And each element can occur atmost in two different sets.

I want to perform an operation on these sets but avoid duplicates or missing any element. Problem: Find out which all of these n sets should be removed because they are covered by other sets.

E.g. [a,b,c]; [a]; [b]. Remove [a], [b] since both are covered by the first one.

E.g. [a,b,c]; [a]; [b]; [c,d]. Remove [a,b,c] since all three elements are covered by remaining sets. Note: here [a],[b] alone is not valid answer since 'c' is being duplicated. Similarly [a],[b],[c,d] is not valid answer since 'd' will be missed if removed.

like image 251
ArunR Avatar asked May 31 '13 06:05

ArunR


2 Answers

I think that this is the Exact Cover problem. The last constraint—that each element is in at most two sets—doesn't seem to me to fundamentally change the problem (although I could easily be wrong about this). The Wikipedia web page contains a good summary of various algorithmic approaches. The algorithm of choice seems to be Dancing Links.

like image 113
Ted Hopp Avatar answered Oct 13 '22 10:10

Ted Hopp


I think this is a case of a 2-sat problem that can be solved in linear time using a method based on Tarjan's algorithm.

  1. Make a variable Ai for each set i. Ai is true if and only if set i is to be included.
  2. For each element that appears in a single set add a clause that Ai=1
  3. For each element that appears in 2 sets i and j, add clauses (Ai && ~Aj) || (~Ai && Aj). These clauses meant that exactly one of Ai and Aj must appear.

You can now solve this using a standard 2-sat algorithm to find whether this is impossible to achieve or a satisfying assignment if it is possible.

For a case with V sets and N elements you will have V variables and up to 2N clauses, so Tarjan's algorithm will have complexity O(V+2N).

like image 25
Peter de Rivaz Avatar answered Oct 13 '22 09:10

Peter de Rivaz