Minimal Sets over Monotone Predicates

This post describes a very nice use of binary search. I learned about it from a paper by Joao Marques-Silva, Mikolas Janota, and Anton Belov.

Let's fix the universe to be $U=\{0,1,\ldots,m-1\}$. Whenever I say ‘set’ I mean ‘subset of the universe’.

Problem. Many problems reduce to the following one: Given a non-empty upward-closed family of sets, find one of its minimal sets. As an example, take the family of sets $\{\{0\},\{1\},\{0,1\},\{0,1,2\}\}$. It's upward closed: If $X$ is in the family then so are all $Y\supset X$. Its minimal sets, one of which we want to find, are $\{0\}$ and $\{1\}$. We can ask only questions of the form ‘is set $X$ in the given family?’

A simple solution. I bumped into this problem while working on refinement for parametric analyses. The solution I found was the following. We are given ${\cal A}\subseteq \wp(U)$. We maintain a current candidate $X$. The invariant is that $X\in{\cal A}$; the variant is that $|X|$ decreases. We establish the invariant by setting $X=U$. We decrease the size as follows: for each element, we throw it away if possible. More precisely, we iterate the elements $u$ of $U$. If $X-\{u\}$ is still in $\cal A$, then we remove $u$ from $X$.

Clearly, this algorithm asks exactly $m$ questions. Also, this solution finds the last set from $\cal A$, lexicographically. (The last set from $\cal A$ is also minimal.)

Lower bound. Is $m$ questions the best we can do? In the worst case, yes. Here is why. Consider the families of sets with exactly one minimal set: $$ {\cal A}_X = \{\,Y\mid X \subseteq Y \subseteq U\,\} $$ There are $2^m$ such families. To identify one of them, we need $m$ bits of information.

At this point I stopped looking for a better solution. I did so despite being told by Mikoláš Janota that better is possible. My attitude was: Improvements to the average case are tricks, not algorithms. I now think that that is a very bad attitude.

A better solution. The previous solution goes through $0,1,\ldots,m-1$ and says

drop $0$,	drop $1$,	$\ldots$	drop $u_0-1$,	keep $u_0$,
drop $u_0+1$,	drop $u_0+2$,	$\ldots$	drop $u_1-1$,	keep $u_1$,
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
drop $u_{k-2}+1$,	drop $u_{k-2}+2$,	$\ldots$	drop $u_{k-1}-1$,	keep $u_{k-1}$
drop $u_{k-1}+1$,	drop $u_{k-1}+2$,	$\ldots$	drop $m-1$

and then returns the solution $\{u_0,u_1,\ldots,u_{k-1}\}$.

The long runs of drops are wasteful, if the output is small. The trick is to use binary search to find the next element to keep.

We start by finding $u_0$. To do so, we find the biggest $v$ such that $\{v,v+1,\ldots,m-1\}\in{\cal A}$. Why? First: If $\{u_0,u_1,\ldots,u_{k-1}\}\in{\cal A}$, then $\{u_0,u_0+1,\ldots,m-1\}\in{\cal A}$. Second: If $\{v,v+1,\ldots,m-1\}\in{\cal A}$, then $v\le u_0$; otherwise, $\{u_0,u_1,\ldots,u_{k-1}\}$ wouldn't be the last element of $\cal A$.

In general, we found some prefix $u_0,u_1,\ldots,u_{i-1}$ and we search for $u_i$. Now we look at sets of the form $$\{u_0,u_1,\ldots,u_{i-1}\}\cup\{v,v+1,\ldots,m-1\}$$ and identify the biggest $v$ for which the set is in $\cal A$.

The second trick is that we use open-ended binary search. If you are familiar with it, then it's safe to skip this paragraph. The simplest example of open-ended binary search is the following: Consider a function $f:\mathbb{N}\to\{0,1\}$ such that $f(i)\le f(i+1)$ for all $i$. We want to find the smallest $i$ such that $f(i)=1$. In the first phase we find some $i$ such that $f(i)=1$. We do so by evaluating $f(1)$, $f(2)$, $f(4)$, $f(8)$, $f(16)$, and so on. After this first phase, we can use normal binary search. We will need the following observation: If the solution is $i$, then the runtime is $\sim \lg i$.

The time needed to find $u_i$ is roughly $1+\lg(u_i-u_{i-1})$. The total runtime is $1+k+\lg u_0 + \lg(u_1-u_0) + \cdots + \lg(u_{k-1}-u_{k-2})+\lg(m-u_{k-1})$. Let us denote the arguments of the logarithms by $x_0,\ldots,x_k$. With this notation, the worst runtime is $$\begin{align} &\text{maximum of}&&1+k+\lg(x_0x_1\cdots x_k) \\ &\text{given that}&&x_0+x_1+\cdots+x_k=m \end{align}$$ The maximum is achieved when $x_0=\cdots=x_k=m/(k+1)$. (This can be shown by using Lagrange multipliers.) Thus, the maximum runtime is $\sim k+k\lg(m/k)$. This runtime depends on two parameters: $m$ describes the input, and $k$ describes the output.

I think it is clear now that this is not ‘just a trick’, but a cute algorithm. I learned at least the following:

1. If you can't improve the worst-case, try to improve something else.
2. Average case analyses are sometimes difficult because you lack a distribution that describes the inputs realistically. In that case, try to improve the runtime when seen as a function of both input size and output size.
3. Listen more carefully to what Mikoláš says. :)

References. If you want to find out more, look at the following articles:

1. [Marques-Silva et al, Minimal Sets over Monotone Predicates in Boolean Formulae, 2013]: This is the paper from which I learned the algorithm presented above. In it, you will also find another (older) algorithm with the same asymptotic performance.
2. [Marques-Silva, Janota, Computing Minimal Sets on Propositional Formulae I: Problems & Reductions, 2014]: Read this if you didn't believe me that many other problems reduce to this one.