[Solved]: Is it possible to always construct a hamiltonian path on a tournament graph by sorting?

Problem Detail: 

Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order:

$\qquad \displaystyle a \leq b \iff (a,b) \in E \lor \left(\exists\, c \in V. a \leq c \land c \leq b\right)$

For context, this came from an observation that the inductive construction in the above page seems to be equivalent to insertion sort using the given order. Is it possible to use other sorting algorithms?

Asked By : Tim Dumol

Answered By : Raphael

I assume that you intend $\leq$ to be the reflexive and transitive closure of $E$, or directed reachability, that is $\leq$ is really the smallest fixpoint of the equivalence you give:

$\qquad \displaystyle a \leq b \iff \exists\, v_0 \dots v_n. a \to v_o \to \dots \to v_n \to b$

with $n \geq 0$ and $v \to u \iff (v,u) \in E$.

The key argument here is that $\leq$ is indeed a total order. If it is, you can use it for sorting, and the result is by definition of $\leq$ a Hamiltonian path: consider the result of the sort $v_1 \dots v_n$. If there were no edge between $v_i$ and $v_{i+1}$, by $V_s = v_i \leq v_{i+1}$ there is $v \in V$ such that $v_i \leq v \leq v_{i+1}$. This contradicts that $\leq$ is a (total) order and $V_s$ is sorted with respect to $\leq$.

Unfortunately, $\leq$ is not an order relation: it is not antisymmetric. Consider the small tournament based on $K_4$:

^[source]

Here, $a \leq d$ and $d \leq a$ (directed cycles are the culprits!) but $a \neq d$. So $\leq$ is only a (well-)quasi-order and there is no such thing as a sorted node list.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2646

 Ask a Question

 Download Related Notes/Documents