28
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What's the 'multiset' lattice ? $\endgroup$ – Suresh Venkat Nov 11 '11 at 4:45
  • 1
    $\begingroup$ It's the lattice whose elements are mappings X -> N, meet is elementwise min and join is elementwise max. It can be generalized to any lattice instead of N as the codomain. $\endgroup$ – jkff Nov 11 '11 at 5:45
15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow, such a simple idea! Thanks - I'll give some thought to whether this seems optimal or not :) $\endgroup$ – jkff Nov 12 '11 at 4:23
  • $\begingroup$ It's actually even less than w log n, since the sum of chain lengths is n. I guess the maximum is around w log (n/w). $\endgroup$ – jkff Nov 12 '11 at 4:37
  • $\begingroup$ OK, for linear orders this gives binary search, for a subset lattice this gives C(n,n/2) log(2^n/C(n,n/2)) ~ exp(n)*n. Not too fast, but doesn't look too suboptimal either, as there may actually be that many answers. However to find one maximal subset, you need binary search over just any one chain - this is great and I now call myself stupid for not thinking of it. Thanks again! $\endgroup$ – jkff Nov 12 '11 at 4:48
  • 2
    $\begingroup$ I think $w$ disjoint chains give you a lower bound of at least $w + \log n$ (for deterministic algorithms). Think of an adversary who "hides" a single solution in the last chain queried. A randomized lower bound of $\Omega(w)$ should follow from Yao's minimax principle. Finding a single element with complexity $w + \log n$ might be interesting. $\endgroup$ – Sasho Nikolov Nov 13 '11 at 3:02
  • 1
    $\begingroup$ @YanKingYin A lattice cannot be the union of (more than one) disjoint chains, because each two elements must have a supremum. A poset is a union of disjoint chains if it can be partitioned so that elements from different parts are incomparable and elements within the same part admit a total order. $\endgroup$ – Sasho Nikolov Dec 1 '14 at 18:36
9
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Heh, sounds not too inspiring compared to log(n) :) but thanks anyways! $\endgroup$ – jkff Nov 11 '11 at 5:46
  • $\begingroup$ But that's the point. Without data structures you can't get log n even for s totally ordered set, because all you can do is scan. It's actually a really nice question to try and find a BST equivalent. $\endgroup$ – Suresh Venkat Nov 11 '11 at 14:29
  • $\begingroup$ Well - I'm talking about the complexity in terms of the number of evaluations of predicate P, not the comparison predicate. $\endgroup$ – jkff Nov 11 '11 at 15:08
  • 1
    $\begingroup$ In a sense yes, but that's far from being the complete answer — eg it doesn't give bisection for the 1d or 2d cases :) what do you suggest to do with the roots? $\endgroup$ – jkff Nov 11 '11 at 18:05
  • 1
    $\begingroup$ Not sure yet. thinking out loud. But it's an excellent question. $\endgroup$ – Suresh Venkat Nov 11 '11 at 18:07
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'm afraid I don't understand the first paragraph. In your reduction, do you have all n-bit strings in the poset S and are they given as part of the input? If so, we can go through all strings in polynomial time. $\endgroup$ – Yoshio Okamoto Nov 11 '11 at 13:04
  • 1
    $\begingroup$ @YoshioOkamoto: I think that the assumption in that paragraph is that the comparison in S is given as a Boolean circuit. (But that has nothing to do with search in a poset and therefore not interesting to me.) $\endgroup$ – Tsuyoshi Ito Nov 11 '11 at 16:06
  • $\begingroup$ @Tsuyoshi: Thank you. That makes a lot of sense. $\endgroup$ – Yoshio Okamoto Nov 11 '11 at 22:16
4
$\begingroup$

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

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