Checking if the mimimum is unique

Question

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

Answer 1

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.