1
$\begingroup$

I have a partially ordered set of numbers, represented as a vector<set<int>> (e.g. if $2 \preceq 4$ in this order, then poset[2] contains 4). Given 2 elements $x$ and $y$, what is an efficient way to find all their minimal upper bounds (that is, those which aren't greater than any other upper bound, but there may be other upper bounds which aren't comparable to them)?

If I also maintain an inverse relation (i.e. inverse_poset is also a vector<set<int>> and inverse_poset[4] contains 2), I can do this:

  1. compute intersection of poset[x] and poset[y];
  2. for each element z of intersection, check if inverse_poset[z] and intersection have a common element other than z. If not, z is a minimal upper bound.

Is there a better way? Especially one which doesn't need inverse_poset?

EDIT: I didn't make it clear in the initial question, but new elements and edges can be added to the poset over time (but not removed). So any preprocessing should ideally be cheap to maintain when they are.

$\endgroup$
4
  • $\begingroup$ @Dmitry That would give one minimal upper bound, but not all of them (or am I missing something?). $\endgroup$ Apr 29 at 18:44
  • $\begingroup$ @Dmitry Actually it can be extended to work: iterate over the intersection in topological order, add an element to the output set if it isn't greater than any element already there. Still, not cheap, I hope there is a better answer. $\endgroup$ Apr 29 at 18:52
  • $\begingroup$ Can you define "better"? How would you measure "better"? Do you want to measure that by runtime to compute this? Are you interested in solutions that might have faster performance in some cases even if they're not asymptotically faster in the worst case? Are you measuring by worst-case asymptotic runtime? Are you willing to do some precomputation to make subsequent queries faster? Is your definition of "better" based on ease of programming instead of running time? Something else? $\endgroup$
    – D.W.
    Apr 30 at 17:58
  • $\begingroup$ "Do you want to measure that by runtime to compute this? Are you interested in solutions that might have faster performance in some cases even if they're not asymptotically faster in the worst case?" Yes to both. "Are you willing to do some precomputation to make subsequent queries faster?" Yes (as I already do with the inverse relation). However, new nodes/edges can be added over time, so this precomputation should ideally not have to be rerun each time. $\endgroup$ May 1 at 7:52

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.