3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is "it" in "If it exists"? ​ ​ $\endgroup$ – user12859 Jun 17 '16 at 20:06
  • 1
    $\begingroup$ Topological sort? $\endgroup$ – Nicholas Mancuso Jun 17 '16 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$ – Werner Thumann Jun 17 '16 at 21:20
4
$\begingroup$

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.

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