# The sorting problem for partially ordered sets

I have two questions about sorting for posets, one easy and one hard:

Easy: Suppose we have a set of objects and a partial order. Given any two objects such that $a \leq b$, we want to delete $b$ from the set. Is there a sub-quadratic time algorithm that can accomplish this, perhaps for some suitable data structure?

Hard: suppose we actually want to sort the list by putting it into some suitable data structure (such as a directed graph). Does there exist a nice data structure leading to a sub-quadratic time sorting?

The second is the natural generalization of the sorting problem to posets. The first is an easier variant that will suffice for this application.

• How is the partial order given to you? What do you mean by "sorting" in the second question? Are you looking for a fast topological sorting algorithm? Sep 7, 2017 at 7:26
• The partial order is given the same way as a linear order - as a comparison function that can return which of two objects is greater, or now additionally return a special value if they are incomparable. Sep 7, 2017 at 14:12
• For the second question, I would have been happy to put the elements in a DAG. However, I am now wondering whether I should split these into two questions... Sep 7, 2017 at 14:16
• Splitting them is probably a good idea. Sep 7, 2017 at 14:18
• What operations do you want the data structure to support? Also, the site normally works best when you ask only one question per question. I'd suggest you edit the question to remove the 'hard' one from this post and (if you're still interested in it) ask it separately in a separate question.
– D.W.
Sep 7, 2017 at 22:34

The set is built out of pairs of objects $a_i, b_i$ where $a_i < b_i$ and there exists no order between $a_i < b_j$ when $i\neq j$.