Assume we have a finite set $X$ of elements and any relation $\preceq$ on $X$. Such a relation may or may not generate a reflexive transitive anti-symmetric relation $\leq$ on $X$ (a partial order). Recall:

reflexive: We always have $x\leq x$.

transitive: If $x\leq y$ and $y\leq z$ then also $x\leq z$.

anti-symmetric: If $x\leq y$ and $y\leq x$ then $x=y$.

I'm looking for an efficient algorithm that decides whether $\preceq$ extends to a partial order and if yes, returns one or one with uniform probability or all possible orderings of $X$ which respect the partial order.

This naturally decomposes into two subtasks (not claiming that the best algorithm decomposes this way):

  1. Decision whether $\preceq$ extends to $\leq$ or, in other words, extending by transitivity does not violate anti-symmetry. If it does, describing the partial order $\leq$.

  2. Finding the possible orderings.

The second points is related this question.

  • $\begingroup$ What is "it" in "If it exists"? ​ ​ $\endgroup$
    – user12859
    Jun 17, 2016 at 20:06
  • 1
    $\begingroup$ Topological sort? $\endgroup$ Jun 17, 2016 at 20:37
  • $\begingroup$ By "it" I mean the generated partial order. Of course I am wrong when stating that the equivalence classes are totally ordered sets, I have to edit the question (which I will do soon). But thanks Nicholas Mancuso, I guess topological sort is the keyword I was looking for and I will have a look at it. $\endgroup$ Jun 17, 2016 at 21:20

1 Answer 1


You can efficiently test whether $\preceq$ extends to a partial order using topological sorting. Form a directed graph with vertex set $X$ and with an edge $x \to y$ whenever we have $x \preceq y$ and $x \ne y$. Then $\preceq$ extends to a partial order if and only if this graph has no cycles, which can be checked in linear time (e.g., by topologically sorting the graph).

Moreover, we can describe a minimal partial order $\le$ that is consistent with $\preceq$, as follows. Compute the transitive closure of this graph. Now declare $x \le y$ iff there's an edge $x \to y$ in the transitive closure, or $x=y$. (Equivalently, declare $x \le y$ iff $y$ is reachable from $x$ in zero or more steps, in the graph derived from $\preceq$.) By construction, the relation $\le$ defined in this way will automatically be reflexive and transitive; if the original graph has no cycles, then it is easy to prove that the relation $\le$ will be anti-symmetric as well and thus will be a partial order.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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