4
$\begingroup$

Assume that we have a non-empty finite lattice $(L,\leq)$ and a monotone Boolean-valued function $f : L \rightarrow \mathbb{B}$ (i.e, for every $x,y \in L$, if $f(x)=\mathbf{true}$ and $x \leq y$, then $f(y) = \mathbf{true}$).

What is an efficient algorithm to compute the frontier set of $f$, i.e., the elements $x \in L$ such that $f(x) = \mathbf{true}$ for but no element $y \leq x$, we have $f(y) = \mathbf{true}$? Alternatively, what is an efficient algorithm to compute the co-frontier set of $f$, i.e., the elements $x \in L$ such that $f(x) = \mathbf{false}$ but for all elements element $y \geq x$, we have $f(y) = \mathbf{true}$?

The algorithm can use the following operations:

  • Get the least element of $L$
  • Get the maximum element of $L$
  • For some element $x \in L$, compute the direct predecessors of $x$, i.e., the elements $y \in X$ with $y \leq x$, but for no $z \in L$, there is $y \leq z \leq x$).
  • For some element $x \in L$, compute the direct successors of $x$, i.e., the elements $y \in X$ with $y \geq x$, but for no $z \in L$, there is $y \geq z \geq x$).
  • Evaluate $f$ on some element of the lattice

The algorithm should minimize the number of calls to the oracle $f$. It can be assumed that the number of direct successors or predecessors of some element is constant and "small".


Some remarks that shall not be seen as part of the problem formulation:

I did a search on algorithms for this already and found a few papers that are not fully irrelevant for this problem. However, they either do not answer the problem, or they are tied to certain application domains, which makes it hard to even find out with certainty if they are related or not. An example is "Maximal Antichain Lattice Algorithms for Distributed Computations" by Vijay K. Garg.

The types of lattices that I am actually interested in are direct products of subsets of $\mathbb{N}$ and $\mathbb{B}$. The problem is is kind of an optimization problem, where $f$ tells us if some "quality requirement" vector is feasible or not.

Thanks!

$\endgroup$
  • $\begingroup$ I think we had a similar question sometime ago but I might be mistaken. I will post a link if I find it. $\endgroup$ – Kaveh Jun 17 '13 at 18:46
  • 1
    $\begingroup$ cstheory.stackexchange.com/questions/8923/… $\endgroup$ – Sasho Nikolov Jun 18 '13 at 4:43
  • $\begingroup$ Should it say "a non-empty finite lattice" so the first two operations make sense? $\;\;\;\;$ $\endgroup$ – user6973 Jun 18 '13 at 5:20
  • $\begingroup$ close as duplicate ? $\endgroup$ – Suresh Venkat Jun 18 '13 at 20:42
  • $\begingroup$ Suresh, go ahead with closing it if you want. By the way: I ended up using an algorithm that works bottom-up instead of the ones given in the other thread. The reason is that for the application that I have in mind, the complexity of evaluating the function actually rises with the position of an element in the lattice. Note that I couldn't find the other other post on google as it was using terms like "monotonic predicate" rather than "monotone function" and "poset" rather than "partially ordered set", which I simply didn't recognize as being good search words. $\endgroup$ – DCTLib Jun 19 '13 at 19:20

Your Answer

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

Browse other questions tagged or ask your own question.