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.
Take a worst case scenario. 

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

This means that to know whether you can delete an element you need to check it against every other element resulting in a quadratic general case. 

The best data structure to avoid that is where each node has a direct reference to which nodes it is greater or equal to. But to build that you need a quadratic algorithm.