1
$\begingroup$

We have a finite poset and its subset $S$.

We can enumerate elements of $S$ using an iterator.

I need to check if there are more than one minimal elements of $S$ (regarding the above poset).

The best thing I came up with is to construct the graph of all elements of $S$ and then check it for minimal elements. But this:

  1. requires to enumerate all elements of $S$ (while I would prefer to interrupt the calculating in the middle as soon as we get $2$ minimal elements);

  2. may use much memory.

Is there a better way (without enumerating all $S$)?

$\endgroup$
  • 1
    $\begingroup$ How is the poset encoded? $\endgroup$ – Zach Langley Jan 15 '18 at 20:45
  • $\begingroup$ @ZachLangley I can check a<b for every elements a, b of the poset. (Actually the elements of the poset are binary relations between small integers, I check which relation is "stronger".) $\endgroup$ – porton Jan 15 '18 at 21:10
  • $\begingroup$ @ZachLangley The poset is a finite boolean lattice actually, thus $\endgroup$ – porton Jan 15 '18 at 21:10
  • 2
    $\begingroup$ Please edit the question to include that information in the question. Don't just place it in the comments -- we want questions to stand on their own, so people don't have to read the comments to understand what is being asked. $\endgroup$ – D.W. Jan 15 '18 at 21:45
  • 1
    $\begingroup$ @porton The questions on this site are not just for you. They are also for other users who come here to view them. Relevant information should be contained in the question and not require users to read the comments to find it $\endgroup$ – mbomb007 Jan 15 '18 at 22:34
3
$\begingroup$

You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z_1,\ldots,z_n$:

  1. $x,y < z_i$ for all $i$.
  2. $x,y < z_i$ for all $i < n$, and $z_n < x,y$.

The first poset has two minima, and second only one. You can only tell the difference by enumerating over all elements.


If there is a unique minimal element $z$, then $z < w$ for all other elements $w$ (since there is a minimal element below any given element). This allows us to use the following constant space algorithm, which assumes that the elements of the poset are $z_1,\ldots,z_n$:

  • Initialize $t \gets z_1$.
  • For $i=2,\ldots,n$: if $z_i < t$, let $t \gets z_i$.
  • Go over all elements again, and verify that $t \leq z_i$ for all of them.

There is a unique minimal element iff the verification succeeds.

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