2
$\begingroup$

I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is valid, so are all its sub-subsets.

This can clearly take exponential time if, for instance, all subsets are valid. However, there are many instances where significant optimization can be done, because if some subset isn't valid, we don't need to check any supersets of it. This suggests some optimization techniques, such as memoization and pruning, but I’m not sure how to implement them efficiently. Here are two approaches I’ve tried:

Bottom-up: Start with valid singletons and build larger subsets by adding elements. Stop when no more valid subsets can be formed. The challenge is how to avoid checking subsets that contain invalid "sub-subsets" we've already tried.

Top-down: Start with the full set and remove elements one by one. Stop when all remaining subsets are valid. The challenge is how to avoid checking subsets that are already known to be valid, because they are sub-subsets of some previously validated subset.

One strategy would be some kind of "super-memoization," where the memoizer doesn't just check if some subset has been evaluated, but knows to return false if any "sub-subset" of it has already evaluated to false, or to return true if any "super-subset" of it has already evaluated to true. I'm not sure the best way to implement this.

Another strategy, which is probably better than the above, would be to prune the search tree so we don't generate subset combinations to begin with which are supersets of something we've already evaluated false, or which are subsets of some larger subset already evaluated to true. This also seems somewhat subtle.

My questions are:

  1. Does this problem have a name?
  2. Are there standard algorithms or libraries to solve it?
  3. What is the best way to do the memoization and pruning?
  4. Are there any textbooks or literature on this problem?

Any help or advice would be appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

This can be formulated as finding all minimal subsets for a monotone function. Here monotone captures your property about supersets and subsets.

Or, this can be formulated exact interactive learning of a DNF representation of a monotone Boolean function $f:\{0,1\}^n \to \{0,1\}$, i.e., given ability to evaluate a monotone Boolean function $f:\{0,1\}^n \to \{0,1\}$ at arbitrary points, find a DNF representation for $f$. Here 0 represents valid and 1 represents invalid, and $x=(x_1,\dots,x_n)$ represents a subset as follows: the subset contains the $i$th item iff $x_i=1$.

Valiant's algorithm

There is a simple algorithm from Valiant for learning such a DNF formula. (See "Learning disjunctions of conjunctions", Proceedings of Joint Conference on AI, 1985.) The algorithm works as follows:

  1. Let $g$ be the empty DNF formula (i.e., always false).

  2. Pick a random $x \in \{0,1\}^n$. If $f(x)=0$, go back to step 2. Otherwise, if $f(x)=1$, continue.

  3. Find a minimal assignment $w$ such that $f(w)=1$ and the variables set to 1 in $w$ are a subset of those in $x$. This can be done by iteratively flipping a variable that $x$ assigns to $1$, to now be assigned to $0$, and keeping this change if $f$ continues to output $1$, otherwise reverting this change.

  4. Set $g(x) := g(x) \lor (x \ge w)$, i.e., add the set of variables that $w$ assigns to 1 to the list of minimal subsets.

  5. Go to step 2.

As an optimization, you can change step 2 to sample from $\{x \in \{0,1\} \mid g(x)=0\}$. I think such an $x$ can be sampled by iteratively picking a new variable that hasn't been assigned yet, setting it to a random value (0 or 1), and at each step, if there is any DNF clause where all but one of the variables have already been set to 1, set the remaining variable to 0. Continue until all variables have been set, and that is your $x$.

The running time is roughly proportional to the number of terms in the DNF representation, i.e., to the number of minimal subsets.

Testcase minimization

Your problem is also closely connected to testcase minimization and delta debugging. In delta debugging, we typically assume that there is only a single minimal subset, only a few, or only one minimal subset whose size is minimum; and the size of this subset is quite small compared to the total number of variables. The connection is that you have a set of lines of code that exhibit some buggy behavior, and you want to find a minimal/minimum subset of lines that also exhibit the same buggy behavior.

Here is an algorithm that I have seen used for testcase minimization, applied to your problem statement:

  1. Let $S$ be the set of all items. Let $\varepsilon=0.1$.

  2. Repeat forever:

  • Let $S'$ be a random subset of a $1-\varepsilon$ fraction of the items in $S$. If $S'$ is invalid, set $S := S'$, otherwise do nothing.

  • If you've done a few hundred iterations in a row where $S'$ was valid in every one: if $\varepsilon < 2/|S|$, exit the loop, otherwise set $\varepsilon := \varepsilon/2$ and continue the loop.

  1. Test each subset of $S$ obtained by removing a single item from $S$. If any of them is invalid, replace $S$ with that subset and restart step 3. Otherwise, if they are all valid, output $S$.

This outputs a single minimum subset. You can probably repeat many times to collect as many minimal subsets as possible.

$\endgroup$
2
  • $\begingroup$ Thanks. For the first algorithm: how do you know when it has found all of the terms? $\endgroup$ Commented Jul 30, 2023 at 21:11
  • $\begingroup$ @MikeBattaglia, good point, I don't know! That seems like a critical gap, and I don't know how to close it. I suppose if $g(x) = (x\ge w_1) \lor \cdots \lor (x\ge w_m)$ and for each $v$ obtained by setting one bit of some $w_i$ to 0 we have $f(x)=0$, then we can terminate. $\endgroup$
    – D.W.
    Commented Jul 31, 2023 at 3:39

Your Answer

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

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