Exact Lower Bounds for the Number of Comparisons in Selection

Assume we have an optimal algorithm for selecting the $i$-th smallest element of a poset $P$. From Equation 2, it follows that for every $(S,i)\in 𝒞(P,i)$, there is at least one leaf in the decision tree labeled with $\{(S,i)\}$. Hence, there are at least $|𝒞(P,i)|$ leaves, implying that the height of the tree is at least $\lceil \log (|𝒞(P,i)|)\rceil$. $◀$

We can significantly speed up the exploration by caching previous results, even with a simple usage-based ejection policy. Since the search always imposes an upper bound on the number of comparisons, this also includes unsolved problems, for which we record the currently known minimum.

We use the minimax search algorithm to cut off unpromising branches. While searching the possible comparisons of a poset, we keep track of the current best result. The remaining comparisons are searched with a limited depth, ensuring that only solutions improving the current best result are found. At the start of a search, possible comparisons are sorted using a heuristic so that the most promising comparisons are searched for first.

Another pruning criterion, which has already been used in [10], aims to reduce the size of the searched subtree by adding a “useful” comparison to eliminate elements faster. Explicitly, it searches for unordered elements $a$ and $b$ such that $a$ has at least two elements less than it and no elements greater than it and $b$ has at least two elements greater than it and no elements smaller than it, and adds to the poset. The new problem is then searched for a solution using the forward search described above without reducing the number of allowed comparisons. If the new problem is not solvable, then the original problem cannot be solvable either. This is valid because adding a comparison “for free” does not make the problem harder to solve. Connecting a small element to a large element can result in many elements being larger or smaller than $i$ elements. This allows for more elements to be discarded when reducing the poset.

Since $(Q,j)$ is a predecessor of $(P,i)$, $(a,b)$ exists with $\mathrm{red}(Q+ab,j)=(P,i)$ and $V_j(Q+ba)\le V_i(P)$. Therefore, $V_j(Q)\le \max \{V_j(Q+ab),V_j(Q+ba)\}+1=V_i(P)+1$. $◀$

Storing only reduced problems presents a significant challenge to predecessor enumeration. To illustrate this, consider a problem $(P,i)$ and its predecessor $(Q,j)$. We know there exists a comparison $(a,b)$ such that $(P,i)=\mathrm{red}(Q+ab,j)$. However, it is possible that the edge $(a,b)$ is not present in $P$ because either $a$ or $b$ could have been removed during the reduction process. The question arises: How can we undo a comparison that is not visible? Furthermore, even if $a$ and $b$ are not removed during the reduction, there may be other elements that are removed. The challenge is to determine how many elements are removed and what their relationships are.

To address these challenges, we will prove two lemmas. The first lemma shows that after adding a comparison $(a,b)$, at most one of $\{a,b\}$ will be removed by the reduction.

Since $(P,i)$ is reduced, we have $|D_P(c)|\le i$ and $|U_P(c)|\le n-i+1$, where $n=|{\mathrm{\Omega }}_P|$, for every $c\in P$. In particular, this holds for both $a$ and $b$. Let $P^{\prime }=P+ab$ and assume $Q\cap \{a,b\}=\mathrm{\varnothing }$. Observe that $D_{P^{\prime }}(a)=D_P(a)\le i$ and $U_{P^{\prime }}(b)=U_P(b)\le n-i+1$. Thus, for $a$ and $b$ to be removed, we must have $U_{P^{\prime }}(a)\ge n-i+2$ and $D_{P^{\prime }}(b)\ge i+1$. Note that there are no elements between $a$ and $b$, as they are incomparable in $P$ and there is a Hasse arc between them in $P^{\prime }$. Hence, $U_{P^{\prime }}(a)\cap D_{P^{\prime }}(b)=\{a,b\}$, leading to the contradiction $n=|{\mathrm{\Omega }}_{P^{\prime }}|\ge |U_{P^{\prime }}(a)\cup D_{P^{\prime }}(b)|=|U_{P^{\prime }}(a)|+|D_{P^{\prime }}(b)|-|U_{P^{\prime }}(a)\cap D_{P^{\prime }}(b)|\ge n+1$. $◀$

The next lemma shows that the elements removed by the reduction, which are not $a$ or $b$, can be added one after the other in such a way that all the intermediate problems are reduced. Figure 2 exemplifies that this is not trivial – a specific order is necessary for the intermediate problem to be reduced.

Let $R={\mathrm{\Omega }}_P\setminus ({\mathrm{\Omega }}_Q\cup \{a,b\})$ be the set of elements, other than $a$ or $b$, removed by the reduction. It is easy to see that for every $c\in R$, the problem $(P^{\prime },i^{\prime })$ where $P^{\prime }={P|}_{{\mathrm{\Omega }}_P\setminus \{c\}}$ and $i^{\prime }=i-1$ if $|U_{P+ab}(c)|\ge n-i+2$ and $i^{\prime }=i$ otherwise is a predecessor of $(Q,j)$:

• $\mathrm{■}$

  It is obvious that $(Q,j)=\mathrm{red}(P^{\prime }+ab,i^{\prime })$.

• $\mathrm{■}$

  The problem $(P^{\prime }+ba,i^{\prime })$ cannot be harder than $(P+ba,i)$, hence $V_{i^{\prime }}(P^{\prime }+ba)\le V_i(P+ba)$.

The challenge is to find an element $c$ such that $P^{\prime }$ is reduced. We define the following sets:

Note that $R=R^{-}\cup R^{+}$. The elements in $C^{-}$ and $C^{+}$ are critical: If $P^{\prime }$ is not reduced, it is because one of these elements can no longer be the $i^{\prime }$-th smallest. To avoid this, we need an element $c\in R^{+}$ that is smaller (in $P$) than all elements in $C^{-}$. By symmetry, any element $c\in R^{-}$ larger than all elements in $C^{+}$ works as well. We first show that if we have an element in $R^{-}\cap C^{-}$ or $R^{+}\cap C^{+}$, then this is the case as

Assume we have $c\in C^{+}$ and $e\in C^{-}$, but $c{\nleqq }_{P}e$. Then the sets $U_P(c)$ and $D_P(e)$ are disjoint, leading to the contradiction $|U_P(c)|+|D_P(e)|=n+1>|{\mathrm{\Omega }}_P|$.

The second step is to show that if $R^{-}\cap C^{-}=\mathrm{\varnothing }$ and $R^{+}\cap C^{+}=\mathrm{\varnothing }$, we can pick any $c\in R$. We show:

Assume we have $c\in R^{-}$ and $e\in C^{+}$. By another counting argument we observe that the sets $D_{P+ab}(c)$ and $U_P(e)$ cannot be disjoint: Assuming $D_{P+ab}(c)\cap U_P(e)=\mathrm{\varnothing }$ leads to the contradiction $|D_{P+ab}(c)|+|U_P(e)|\ge n+2$. Thus, $(e,c)\in P+ab$. Hence, we have either $e{\le }_{P}c$ or $e{\le }_{P}a$. If $e{\le }_{P}a$ but $e{\nleqq }_{P}c$, we have to show $a\ne e$ to conclude $e\in R^{+}$. Assume $a=e$. Then $U_P(a)\setminus \{a\}$ and $D_{P+ab}(c)$ must be disjoint, as $e{\nleqq }_{P}c$. We obtain the contradiction $|U_P(a)\setminus \{a\}|+|D_{P+ab}(c)|\ge n+1$. By symmetry, we also obtain:

which concludes the proof. $◀$

The set of predecessors for a given problem $(P,i)$ can be split into the following three subsets, which we compute in that order.

1. 1.

   Predecessors on the same set of elements.

2. 2.

   Predecessors with exactly one additional element that is involved in the comparison.

3. 3.

   Predecessors with additional elements of which at least one is not part of the comparison.

Of the predecessors to the problems in $A_k$, those that actually require $k+1$ comparisons (those not in $A_k$) make up the set $A_{k+1}$. We describe the steps to compute the three sets below.

Our goal is to find all posets with $n$ elements that result in poset $P$ after inserting a comparison . Each edge in the Hasse diagram of $P$ potentially represents a comparison by which $(P,i)$ can be obtained from a predecessor. A challenge arises from transitive relations, as the insertion of a single comparison can lead to the insertion of multiple transitive relations. This is illustrated in Figure 3. Removing a comparison from (1) can result in either (2) or (3). Therefore, both (2) and (3) are potential predecessors, even though the same comparison is removed each time.

After enumerating the potential predecessors, we check for each one whether it is a predecessor of $(P,i)$. For a potential predecessor $(Q,j)$ where $(P,i)=\mathrm{red}(Q+ab,j)$, we check whether $(Q+ba,j)$ can be solved using at most $V_i(P)$ comparisons. This is done by checking whether $\mathrm{red}(Q+ba,j)$ is contained in one of the sets $A_k$ for $k\le V_i(P)$, which have already been computed.

We construct the potential predecessor for this case as follows. We add a new element to the poset $P$ and enumerate all possibilities for the relation between the new element and the existing elements. We want the predecessor to be reduced, thus it is crucial to ensure that the new element cannot be immediately reduced and that no existing elements can be reduced either. Since the new element is either smaller or larger than the $i$-th smallest element being searched for, either the $(i+1)$-th smallest or the $i$-th smallest element is searched for in these predecessors. Furthermore, for each $(Q,j)$ obtained this way, there must exist elements $a$ and $b$ such that $\mathrm{red}(Q+ab,j)=(P,i)$. This is required for $(Q,j)$ to be a potential predecessor, and since we additionally want the new element to be part of the comparison, we mandate that either $a$ or $b$ is the new element. Checking whether the potential predecessors constructed this way are predecessors is done in the same way as in the preceding step.

For the correctness of our approach, note that if we have an arbitrary reduced predecessor, then by removing all elements that are not present in $P$, with the exception of $a$ and $b$, we obtain another reduced predecessor. We get this by induction on the number of elements removed using Lemma 10. If both $a,b\in {\mathrm{\Omega }}_P$ then this predecessor is enumerated in the first step. Otherwise, as proven in Lemma 9, if one of $a$ or $b$ is in ${\mathrm{\Omega }}_P$, the predecessor is enumerated in this second step. In the next step, we will iteratively enumerate all predecessors by adding additional elements to the ones already found. This way, we will discover the arbitrary predecessor we started with.

Starting with the predecessors computed in the first two steps, new elements are iteratively inserted. We alternate between generating new potential predecessors and checking which of those are actually predecessors. We stop when no new predecessors are found or when we reach an upper limit on the number of elements. New potential predecessors are generated by adding a new element to each predecessor and enumerating all possible relations with the existing elements. When inserting a new element, it is important to note that it may no longer be the $i$-th smallest but rather the $(i+1)$-th smallest element being searched, similar to the second step. We only consider potential predecessors that are reduced and of cause by the addition of the comparison and subsequent reduction, the resulting problem $(P,i)$ should be obtained anew.

Each time an element is removed from a poset during reduction of a problem, a possible consequence is, that now we are looking for the $(i-1)$-th instead of the $i$-th element. Therefore, if $(P,j)$ is a problem appearing in an algorithm selecting the $i$-th smallest of $n$ elements, then $i-j\le n-|{\mathrm{\Omega }}_P|$. An optimization we apply to the backward search is to ignore any problems that violate this inequality. They cannot contribute to the solution. E.g. no problem with $n=6$ and $i=2$ can lead to a problem with $n=7$, $i=4$.

As the theoretical upper bounds are too high in practice, the program uses an iterative deepening approach. It starts with an upper bound that corresponds to the theoretical lower bound, derived by Lemma 1 from the smaller values for $n$ and increments this bound until a solution is finally found. As it is not possible to save which posets are ignored due to the guessed upper bound without considerable effort, the backward search is restarted several times. Although results from previous rounds are not used, the search space can be considerably reduced, making the program more efficient.

This number of edges in the Hasse diagram of a poset is a lower bound to the number of comparisons that must be removed until the unordered poset is reached. Since at most one comparison can be removed in each step, all posets containing too many Hasse arcs can be discarded, as they cannot lead to an unordered poset with the remaining comparisons.

The backward search can be ideally parallelized by performing the calculation of the predecessors in parallel. The only two bottlenecks are read access to the cache and the efficient merging of all partial results. As shown in Table 2 for $n=13$ and $i=7$, it can be seen that the backward search scales well with the number of cores. To set the different times in relation to the number of cores, the efficiency was determined, which represents a direct correlation between the two variables. This can be calculated as follows

The higher the efficiency, the better the time scales with the number of cores.