## Posts Tagged ‘hamiltonian path’

### Tournament graph and Hamiltonian Path

November 11, 2010

Well,

Those of you who are unaware of tournament graph and hamiltonian path, you can look here and here. Ramprasad gave me the following interesting problem to think about.

Problem : Given a tournament ( I will omit the suffix “graph” as it is obvious in the context of graph theory ), construct a hamiltonian path in polynomial time.

Solution : When I first heard the problem, I was even wondering how to prove first that all tournament indeed always have an hamiltonian path. And that too, we need to find it in polynomial time..Phew! But I believe that if you comeup with an algorithm, that itself gives you a proof!!

He gave me a hint : given that you already have explored some path $v_1,\dots,v_k$ how can you extend it for a given vertex $v$? That is, of course, if the path has not covered every vertex :-).

If there is a directed edge from $v_k$ to $v$ there is a natural extension. You just append $v$ to the path. If not, find out two consecutive vertices $v_i, v_{i+1}$ in the path such that the tournament have edges $(v_i,v)$ and $(v,v_{i+1})$ in which case the modified path will be $v_1,\dots , v_i, v ,v_{i+1},\dots, v_k$.

Suppose no such pair exists!!!! Let’s try to see why this can’t be true. Look at, $v_1,v_2$. It has to be the case that either tournament contains edges $(v_1,v),(v_2,v)$ or $(v,v_1),(v_2,v)$. If it is the second case, that $v$ can be just added as a prefix to the path. If it is the first case, than note that tournament must contain $(v_3,v)$ because other wise we can have $\dots, v_2,v,v_3,\dots$. Similarly, we can argue for $v_4,\dots$ giving us the contradiction as we had assumed that edge $(v_k,v)$ is absent from the tournament.

Hence, we can always extend the path as long as there is some vertex we have not yet covered.
Ramprasad gave a simple proof of why a pair $v_i,v_{i+1}$ must exist such that we can extend the path to contain $v_i,v,v_{i+1}$. If we can not add $v$ as a prefix or a suffix to the path. Then look at the vertex with the least index j such that $(v,v_j)$ is an edge. By the definition of the tournament, one of the two edge $(v_{j-1},v) , (v,v_{j-1})$ must be there. But, because j is the least index having an incoming edge in the path, the second edge can not be there. hence we can extend the path to contain $v_{j-1},v,v_j$.

Easy to see that algorithm runs in $O(n^2)$ time as we need to search $O(n)$ vertex to extend the path and repeat it till we  have covered all vertices.

–Saurabh Joshi