Efficient algorithm to find the maximal elements of a partially ordered set

Question

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

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 to do this (minimize the number of comparisons)? I tried building a DAG and doing a topological sort, but just building the graph requires O(n^2) comparisons, which is too many.

I'm doing this in Python, but if you don't know it I can read other languages, or pseudocode.

Answer 1

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

And if you allow O(n^2), since the ordering is transitive, you can just make one pass through the set, keeping a list of all elements that are maximal so far; each new element knocks out any maximal elements that are < it and gets added to the maximal list if it is not < any maximal element.

Answer 2

In the worst case, you can't be faster than O(n^2). Indeed to check that all element are maximal for the poset where no element are comparable, you need to compare every pairs of elements. So it's definitely quadratic in the worst case.

Let me clarify to answer the comment below : I'm claiming that the worst case is attained when the poset is the trivial poset where no two elements are comparable. In this case, all elements are maximal. To check that this is indeed the case, any algorithm doing comparison must perform all n(n+1)/2 comparisons. Indeed, if a comparison say a <-> b is not performed, then the algorithm can't distinguish the trivial poset with the poset where the only relation is a < b so it can't give the correct answer. So any algorithm must be at least quadratic in the worst case.