2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.