# Finding maximal independent sets in an independence system

An independence system is a collection $I$ of subsets of $\Omega$ such that if $A\in I$, then any subset of $A$ is in $I$. These sets are called independent.

Suppose I have an oracle for testing independence. In particular I have an ambient set $\Omega$ and an independence system $I$ of subsets of $\Omega$. I pass a subset $A$ of $\Omega$ to the oracle, and it tells me if $A\in I$. Is there an efficient algorithm for finding all maximal independent sets? I especially care about minimizing the number of calls to the oracle, which is expensive.

I implemented a brute force method (just looping over the powerset) which chokes for inputs sizes above about $n=6$. On the other hand, the Bron-Kerbosch algorithm solves exactly this problem in a special case, and my implementation of it runs quite happily up to around $n=30$. That would be plenty satisfactory to me.

• If you know a little more about the oracle instead of just treating it as a total black box, then more algorithms are available. For example, if you can efficiently test incrementally whether adding a single element to an independent set makes the set dependent, then you can use the algorithm from Bailey and Stuckey (2005). "Discovery of Minimal Unsatisfiable Subsets of Constraints Using Hitting Set Dualization." Jun 28, 2017 at 22:33

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