The sorting problem for partially ordered sets
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.