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):
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$.
Finding the possible orderings.
The second points is related this question.