# Hamiltonian path in a tournament

Exercise: Suggest an effective algorithm finding Hamiltonian path in tournament with $n$ vertices using adjacency matrix T[1..n, 1..n].

Firstly, I proved that such path always exists. It was an easy induction, we can construct such path adding consecutive vertices to it, because each vertex can be added before first vertex in current path or after the last vertex or in other case, for this vertex (j) there exist vertices (i) and (i+1) such that T[ (i), (j) ]=true and T[ (j), (i+1) ]=true, so it can be added between vertices (i) and (i+1).

Basing on this algorithm it is easy to solve this problem in $O(n^2)$. Is it effective?

Because the second part of this exercise is to prove that every algorithm that finds Hamiltonian path in $n$-tournament given by adjacency matrix T[1..n, 1..n] does it in at least $\Omega(n \log n)$ operations of checking matrix T.

I completely don't know how to approach this problem, it seems very hard to prove something for every algorithm (that uses adjacency matrix).

-
I don't have an answer yet but did you guys learn about the lower bound for comparison based sorts? The proof involves $log(n!)$ which is $\Theta(n \log n)$. –  roliu Nov 4 '12 at 10:03

First show that for each permutation of the $n$ vertices you can construct a Tournament whose unique Hamiltonian path is that permutation. Then think of any algorithm as a decision tree. Every time it looks at a cell of the adjacency matrix the answer is either true or false and it takes a different branch in the decision tree. So you start with a set $S$ of $n!$ possible graphs and then, in the worst case, the algorithm always gets an unfortunate answer back (i.e. it sees $T[i,j] = \text{false}$ so it has to take the larger "half" of $S$). Ultimately the binary tree has $n!$ leaf nodes and so there has to be some path with length at least $\log_2(n!)$. The rest falls out... (I hope)