CODEWITHSUNDEEP
algorithmsetcombinatoricsset-intersection
PPenguin
PPenguin

Reputation: 329

Algorithm to find minimal subsets that intersect with list of sets

Problem statement:

Given a list L of sets, find every set X of elements such that:

  1. for all Y in L, the intersection of X and Y is non-empty

  2. the set X is minimal in the sense that no element in X can be removed and still satisfy property #1

I have a feeling this is a known / already studied problem, and I'd like to read up on the algorithms for it. However after reading about various set problems and algorithms, I have yet to find one that matches this. (Or maybe I didn't realize it could be rephrased to match my problem, as such problem transformations are often not obvious to me.)

The closest I've found so far is discussions of something called the "Set Intersection Problem" ( example: https://arxiv.org/abs/1307.0053 ), but that is just looking for elements that are in all the sets. So it is related, but much more restrictive than what I am considering.

I eventually was able to write some algorithms with some heuristic approaches that work okay for my purposes currently, so I really am more interested in finding what this problem is called, or literature references, but interesting code snippets would of course be educational as well.

Upvotes: 1

Views: 179

Answers (0)

Related Questions