2
$\begingroup$

For a given acyclic graph $G$, a topological sort is an ordering $v_1, \dots, v_n$ of the vertices such that the arrows in the graph are all directed forward under that ordering.

Question: can all topological orders of a graph $G$ be obtained from a single ordering by iteratively swapping two vertices that are not connected by an edge?

Motivation. In a certain context I am trying to prove that all topological sorts of an acyclic graph are in fact "equivalent". I want to do this by comparing $v_1, \dots, v, v', \dots v_n$ and $v_1, \dots, v', v, \dots v_n$ where there is no edge between $v,v'$.

Improve this question
$\endgroup$
6
  • $\begingroup$ What do you mean by "iteratively"? Do you mean a single swap, or do you mean a sequence of swaps with some terminating condition? $\endgroup$
    – G. Bach
    Commented Nov 9, 2013 at 16:11
  • $\begingroup$ @G.Bach I want to prove all topsorts equivalent, by showing that topsorts are equivalent if they differ only by a single swap. Thus, I want to know whether any two topsorts can be transformed into one another by applying a sequence of swaps. $\endgroup$
    – Hendrik Jan
    Commented Nov 9, 2013 at 20:56
  • $\begingroup$ This should be possible, and I think the way to go about it is this: take two incomparable (i.e. no edge between them) vertices $v_1$ and $v_2$ and let $V_1$ be the set of all vertices that need to come after $v_1$, and define $V_2$ analogously. To make a swap of $v_1$ and $v_2$ legal, you'll have to think about what to do with the vertices that are in the symmetric difference of $V_1$ and $V_2$ (i.e. the vertices that only depend on one of $v_1$ and $v_2$), and keep them arranged appropriately during the swapping. $\endgroup$
    – G. Bach
    Commented Nov 9, 2013 at 21:15
  • $\begingroup$ @HendrikJan the vertices you want to swap, must they be next to each-other in the sort-permutation? (ie. can you do $\text{swap}\left(v_i,v_j\right)$ with any $v_i,v_j$, or must it be $\text{swap}\left(v_i,v_{i+1}\right)$) $\endgroup$
    – Realz Slaw
    Commented Nov 12, 2013 at 1:44
  • $\begingroup$ @RealzSlaw Good point. My initial idea was to restrict to neighbour swaps, but perhaps that does not work. $\endgroup$
    – Hendrik Jan
    Commented Nov 12, 2013 at 21:11

1 Answer 1

Reset to default
1
$\begingroup$

Let $\tau_1: x_1, x_2, \dots, x_n$ and $\tau_2: y_1, y_2, \dots, y_n$ be two topological orderings of the vertices of graph $G$. Our aim is to show that $\tau_1$ can be transformed into $\tau_2$ by a sequence of swaps, each changing the position of two vertices in the sequence, not connected to each other by an edge of $G$.

Starting from the beginning compare the vertices $x_i$ and $y_i$ and select the first pair that differs. For notational convenience we assume $x_1 \neq y_1$. As $y_1$ must occurs in $\tau_1$ we can find $x_j=y_1$, $j>1$. Thus vertices $x_1, \dots, x_{j-1}$ are all before $x_j=y_1$ in ordering $\tau_1$, but all after $y_1=x_j$ in ordering $\tau_2$. This implies there is no edge in $G$ (in either direction) from $x_j$ to each of $x_1, \dots, x_{j-1}$. Thus we can "legally" swap $x_j$ with each of $x_1, \dots, x_{j-1}$ to get it to the first position. We obtain $\tau'_1: x_j, x_1, \dots, x_{j-1}, x_{j+1}, \dots, x_n$ which has the same first element as $\tau_2$.

Iterate, or invoke induction.

(Thanks for your suggestions and support.)

Improve this answer
$\endgroup$

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.