1

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.

Improve this question
6
  • For set theory, you might have better luck over in mathematics. Stackoverflow is for specific question about specific code. Commented Dec 9, 2023 at 8:48
  • 1
    If you're looking for a set X of minimum size, then the problem can be quite hard, but if you're just looking for a minimal set X then it's extremely easy. Just start with X = union of all the sets and then remove elements from X until you can't remove any element. Commented Dec 9, 2023 at 12:11
  • 6
    You want to enumerate all minimal hitting sets. If you go looking for algorithms, there's an equivalent formulation that involves enumerating minimal set covers. Commented Dec 9, 2023 at 12:12
  • If you want to enumerate all minimal sets X then you can do it this way: start with X = union of all sets; find the next element of X than can be removed; then make two recursive calls, one where this element is removed, and one where this element is marked as "don't remove". Commented Dec 9, 2023 at 12:35
  • @DavidEisenstat I wish I could mark your comment as the answer. Sometimes the appropriate key words are all it takes to open up a world of solutions. Thanks. Commented Mar 1, 2024 at 23:46
Related questions
1048
How can I find the time complexity of an algorithm?
425
Best way to find the intersection of multiple sets?
9
Good algorithm for finding subsets of point sets
Load 6 more related questions Show fewer related questions

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.