Skip to main content
2 of 2
deleted 78 characters in body; added 1 character in body
D.W.
  • 165.6k
  • 21
  • 230
  • 490

This looks equivalent to finding all maximal zeroes of a monotone function, given ability to make oracle queries to the function. Let $f:\{0,1\}^n \to \{0,1\}$ be a monotone Boolean function, and call $x$ a maximal zero if $f(x)=0$ and $f(y)=1$ for all $y\ge x$ (i.e., $y_i \ge x_i$ for all $i$).

This problem has been studied extensively. I believe there are no known polynomial time algorithms. See https://cstheory.stackexchange.com/q/14772/5038, Maximal Elements in a Lower Set, https://cstheory.stackexchange.com/q/18047/5038, How to enumerate minimal covers of a set, and https://cstheory.stackexchange.com/q/14772/5038. I think the concepts of learning DNF representations for monotone boolean functions and monotone dualization will be relevant. I confess I don't fully understand the literature and don't know if there are any algorithms that are good-enough-in-practice.

The relationship: Suppose $\Omega=\{1,2,\dots,n\}$. We can identify the set $A$ with its characteristic vector, which is an element of $\{0,1\}^n$. Now an independence system $I$ determines a function $f$ given by $f(A)=0$ if $A \in I$, otherwise $f(A)=1$. You have oracle access to $f$, and want to find all maximal sets $A$ such that $f(A)=0$.

D.W.
  • 165.6k
  • 21
  • 230
  • 490