Effective algorithm for finding the maximum elements of a partially ordered set

Question

I have a partially ordered set, say A = [x1, x2, ...] , which means that for each xi and xj in the set (exactly) one of the four possibilities is true: xi < xj , xi == xj , xi > xj , or xi and xj comparable.

I want to find the maximal elements (i.e. those elements xi for which there are no elements xj with xi < xj ). What is an efficient algorithm for this (minimize the number of comparisons)? I tried to create a DAG and do a topological sort, but it takes O (n ^ 2) comparisons, which are too many, to plot.

I do this in Python, but if you do not know this, I can read other languages ​​or pseudo-code.

Answer 1

It seems the worst case is O (n ^ 2) no matter what you do. For example, if no elements are comparable, you need to compare each element with every other element to determine that they are all maximum.

And if you enable O (n ^ 2), since the ordering is transitive, you can just go through one set through one set, keeping a list of all the elements that are still maximum; each new element knocks out any maximum elements, it is added to the maximum list if it is not <any maximum element.

Answer 2

In the worst case, you cannot be faster than O (n ^ 2). Indeed, to verify that all elements are maximal for poset, where no element is comparable, you need to compare each pair of elements. Thus, it is definitely quadratic in the worst case.

Answer 3

Suppose you looked at all (n select 2) comparisons, except for one, between x _i and x _j , i! = J. In some scenarios, the only two candidates for maximum values ​​are precisely these two, x _i and x _j .

If you do not compare x _i and x _j , you cannot definitively say whether they are maximal or only one of them.

Therefore, you should check all possible (n choose 2) (O (n ² )) comparisons.

---

Note that this assumes that your partially ordered set is given by a black box that will perform the comparison. If a partially ordered set is specified as the beginning of the graph, you can subsequently find the set of maximum elements in sub-O (n ² ) time.

Answer 4

As the other answers pointed out, the worst difficulty is O (n ^ 2).

However, there are heuristics that can help in practice. For example, if the set A is a subset of Z ^ 2 (integer pairs), then we can eliminate the set of upfront points:

• Sorting along the x axis (for a given value of x say 1, find the point with the maximum value of y, repeat for all values ​​of x) to get a set of candidates maximums, call it y-maxima.
• Similarly, we get the set of x-maxima.
• Cross to get the final set of xy-maximals candidates.

This is the cost of O (n). It is easy to see that any maximal point will be present in xy-maxilla. However, it may not contain maximum points. For example, consider the set {(1,0), (0,1), (2,2)}.

Depending on your situation, this can be quite heuristic. You can follow this with a comprehensive algorithm on a smaller set of xy-maxilals.

More generally, this problem is called the Pareto Frontier calculation problem. Here are some good links:

http://www.cs.yorku.ca/~jarek/papers/vldbj06/lessII.pdf

https://en.wikipedia.org/wiki/Pareto_efficiency#Use_in_engineering_and_economics

In particular, the BEST algorithm from the first link is very useful.