3
$\begingroup$

My problem

Given a partially-ordered set $(S, <)$, I want to compute the set of maximal elements $$ S_{max} =\{a\in S | \nexists b \in S, a < b \} $$

while making as few comparisons as possible between elements.

A couple of examples:

  • $S=\{1, 2, ... P\}$ with the usual comparison operator. Then $S_{max}=\{P\}$. This example is somewhat trivial because any set with a strict total order, as is the case here, has a unique maximal element that can be determined in linear time.
  • $S=\{(x,y)| x,y\in\{1, 2, ... P\}\}$ with the partial ordering $(x,y)<(x',y') \iff x<x' \text{ and } y<y'$ (in English: the set of all pairs of integers between $1$ and $P$, where a pair is strictly smaller than another if both values are pairwise strictly smaller). Then the maximal set is $S_{max}=\{(x,y)\in S|x=P \text{ or } y=P\}$ (in English: the set of pairs with at least one value equal to the maximum value; such pairs are not strictly smaller than any other element, and any other pair is strictly smaller than $(P, P)$).

My real-world use case is in fact the second example, but with $S$ a subset of all possible pairs of integers between $1$ and $P$ (rather than all such pairs). (Feel free to answer either specifically for that case, or more generally.)

Semi-obvious complexity bounds

Assume the set has $N$ elements.

No algorithm can have a best case (and thus an average case) better than $O(N)$: any algorithm, on any input data, must make at least $O(N)$ comparisons, because every element of the set must be compared at least once to another element.

Any algorithm has a worst case in $O(N^2)$: Consider input data with an empty ordering (i.e., there are no elements such that $a<b$). Then, $S_{max}=S$; but to know this, the algorithm needs to compute every pairwise comparison (and see that it fails), which is $O(N^2)$ comparisons.

There is an algorithm that guarantees $O(N^2)$ for any input data: the brute-force algorithm is as follows:

candidate_set := $S$
for all $a,b \in S$:
    if a<b:
        remove a from candidate_set
    if b<a:
        remove b from candidate_set

return candidate_set

In fact, one could even produce a topological ordering of the set in $O(N^2)$ (see Kahn’s algorithm).

Is there a quicker way?

I "only" want the maximal elements, not a full topological ordering, so there might be a quicker way to proceed than $O(N^2)$. Every comparison that yields a true value allows us to eliminate an element from further consideration; therefore, if there is a heuristic to find comparisons that are likely to be true, starting by computing those comparisons first allows us to cut the search space quicker.

For instance, for my use case (see above), I feel the following pseudocode gives a good start in many conditions:

candidate_set := $S$
comparison_targets_set = $CTS$ := $\emptyset$

possible_first_values := $\{x|(x,y)\in S\}$
for $x_0$ in possible_first_values:
    associated_y_values := $\{y|(x_0,y)\in S\}$
    add $(x_0$, max(associated_y_values))$ to $CTS$

# do the same thing by bucketing on second values rather than first values

# then run the brute-force algorithm, but only for comparisons where the right hand side is in $CTS$

The preprocessing steps are all in $O(N)$. Applying the brute-force algorithm afterwards is $O(N\times card(CTS))$ which might be significantly smaller than $O(N^2)$ in practice. I suspect that for uniform I.I.D. random pairs of integers, $card(CTS)\approx \sqrt{N}$: basically, the points are a random blob in 2D, $CTS$ is roughly a subset of the convex envelope, and a random blob of $N$ points has about $\sqrt{N}$ points on its convex envelope. Needless to say, this is not a rigorous proof, but if it is true, then the pseudocode above runs in $O(N^{3/2}$) average time.

$\endgroup$
3
  • $\begingroup$ What assumptions should we make about how the partial order is provided as input to the algorithm? How is it represented? Is it a "black box" where the only thing we can do is enumerate all elements in the p.o. and compare two elements? Are there extra operations that are available? $\endgroup$
    – D.W.
    Commented Jun 25 at 18:33
  • $\begingroup$ @D.W. My concrete problem is (almost) the Pareto front problem, but it got me thinking about a more general problem (i.e. the "black box" version). Certainly the black box version is quadratic in the worst case(s) of input but what of "random" inputs? (I have an idea, but that will be another question - this was alrready two questions in one and you answered both.) $\endgroup$
    – UJM
    Commented Jun 26 at 9:13
  • $\begingroup$ Follow-up question asked: cs.stackexchange.com/questions/168779/… $\endgroup$
    – UJM
    Commented Jun 26 at 12:13

1 Answer 1

3
$\begingroup$

In the worst case, $\Theta(N^2)$ time can be required, for "unfriendly" partial orders. For some partial orders, faster algorithms will be possible, but to achieve better running time, the algorithm will have to be specialized towards a class of partial orders.

In particular, consider the set $S=\{0,1\} \times T$ where $T$ is some set with $N/2$ elements. Make it a partial order: as follows: $(0,t) < (1,t)$, and there are no other relations. Of course if you are given elements of $S$ as pairs, it is easy to find the maximal elements, but if each element of $S$ is assigned a random unique label, and you are given only the labels, then it is possible to show that finding all maximal elements takes $\Theta(N^2)$ time. The intuition is that given a single element of $S$, checking whether it is maximal or not requires comparing to $\Theta(N)$ other elements on average.

For your specific example of a partial order, there are algorithms that run in $O(N \log N)$ time. This is known as the skyline operator or as finding the Pareto-optimal pairs. See, e.g., What are some interesting applications of the skyline problem?, https://arxiv.org/abs/1704.01788, minimum subset of dominating 2D points, An online algorithm to maintain the Pareto frontier elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.