Find if any set is covered by member sets

Question

[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.

Answer 1

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.

Answer 2

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).