Binary search generalizations for posets?

Question

Suppose I have a poset "S" and a monotonic predicate "P" on S. I want to find one or all maximal elements of S satisfying P.

EDIT: I'm interested in minimizing the number of evaluations of P.

What algorithms do there exist for this problem and what properties and additional operations do they require on S?

What about important special cases, such as:

• S is a linear order - then regular binary search works, as long as you have a "find middle" operation
• S is a lattice
• S is a subset lattice
• S is a multiset lattice
• ...

The two latter cases seem particularly important e.g. for experiment design - you have a set of boolean or real parameters, and you wish to find the smallest possible combination of them that reproduces a particular pattern (e.g. a failing test).

Answer 1

I have not thought this through very much, so please correct me if I am wrong.

Say $w$ is the width of the poset.

1. For the poset which is the union of $w$ disjoint chains you need at least $w\log n$ evaluations of $P$ by just applying the standard lower bound on the query complexity of binary search to each chain.

2. Since you give comparisons for free, you can compute a chain decomposition of the poset into $w$ chains for free. Do binary search on each chain to identify the first element that satisfies $P$. Then go over the identified elements and remove any dominated ones. Number of evaluations of $P$ is $O(w\log n)$. This identifies all maximal elements, as there can be at most one maximal element per chain.

---

ADDED: Actually I am seeing a simple recursive algorithm to do much better ($O(n)$) for the lattice of subsets $2^{[n]}$ (EDIT: domotor described the general strategy in his answer). Here I am assuming $P$ is monotonic downwards (i.e. the subsets $\{X: P(X) = 1\}$ form a lower set), which is I think what you mean. So, here is the algorithm to find a member of the lower set:

a) Test $P(\emptyset)$. If 0, then stop.

b) Test $P(\{n\})$.

b.i) If 0, then recurse on $2^{[n-1]}$ (OK, since no set containing $n$ can be in the lower set).

b.ii) If 1, then there exists a member of the lower set in the sublattice $\{X: n \in X\}$. This sublattice is isomorphic to $2^{[n-1]}$ so once again we can recurse. More precisely, we can run the algorithm for $2^{[n-1]}$, but when the algorithm asks to evaluate $P(Y)$, we evaluate $P(X)$ where $X = Y \cup \{n\}$.

So in each step we recurse on a sublattice which is half the size of original one. Overall, we need to evaluate $P$ at most $2n$ times (in fact you can implement the algorithm to evaluate the predicate $n+1$ times as Yoshio points out, since you only need to check $\emptyset$ once).

Answer 2

If $P$ is a tree, then there is a polynomial-time algorithm that constructs an optimal decision tree.

Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders

Answer 3

One recent paper by Daskalakis et al shows that for a poset of size $n$ and width $w$, minimal elements can be found in time $O(wn)$. What's interesting is that in their abstract, they say

It would also be interesting to find efficient static and dynamic data structures that play the same role for partial orders that heaps and binary search trees play for total orders.

Answer 4

For the problem of finding all the maximal elements of $P$ over the lattice of subsets $2^{[n]}$, this amounts to exact inference of a positive boolean function of $n$ boolean variables. If you only care about the number of evaluations of $P$ (not the computational complexity), you can find a survey in Data Mining and Knowledge Discovery via Logic-Based Methods, Chapter 10, section 10.2.4, or in the last paragraph of section 6.1 of this article, which I was pointed to by this answer (beware, the rest of this article deals with computational complexity, not just the complexity of evaluating $P$).

Answer 5

If S is part of the input, then the problem of finding a maximal element already becomes ``NP-hard'' (if we think of the lattice such that its elements are n bit long strings), e.g. you can say $x<y$ if CNF(x) is not true and CNF(y) is true for some fixed CNF.

Also, there might be many maximal elements satisfying P, so even to output all of them might take a long time, so I think there is only hope to find one maximal.

In general, binary search works if you can recursively select elements such that after you are left either with the above elements, or the above elements are deleted, and in every such sets a fixed ratio of the elements are deleted.

Eg. if S is a fixed dimensional grid, then there is a fast algorithm: Always halve one coordinate while keeping the others minimal, so ask e.g. in the first step (n/2,0,...,0).

One important related theorem is the Tarski fixed point theorem, where instead of P you have a monotone mapping from a lattice to itself. The theorem says that the fixed points form a lattice. We proved with Jaroslaw Byrka and Paul Duetting that in this setting if the lattice is a d-dimensional grid, then you can find a fixed point in about $n^d$ time where the algorithm is a simple generalization of binary search.