1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Yuval Filmus Sep 7 '17 at 7:26
  • $\begingroup$ 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. $\endgroup$ – Mike Battaglia Sep 7 '17 at 14:12
  • $\begingroup$ 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... $\endgroup$ – Mike Battaglia Sep 7 '17 at 14:16
  • $\begingroup$ Splitting them is probably a good idea. $\endgroup$ – Yuval Filmus Sep 7 '17 at 14:18
  • $\begingroup$ 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. $\endgroup$ – D.W. Sep 7 '17 at 22:34
1
$\begingroup$

Take a worst case scenario.

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$.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.