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 how can you extend it for a given vertex ? That is, of course, if the path has not covered every vertex :-).

If there is a directed edge from to there is a natural extension. You just append to the path. If not, find out two consecutive vertices in the path such that the tournament have edges and in which case the modified path will be .

Suppose no such pair exists!!!! Let’s try to see why this can’t be true. Look at, . It has to be the case that either tournament contains edges or . If it is the second case, that can be just added as a prefix to the path. If it is the first case, than note that tournament must contain because other wise we can have . Similarly, we can argue for giving us the contradiction as we had assumed that edge 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 must exist such that we can extend the path to contain . If we can not add as a prefix or a suffix to the path. Then look at the vertex with the least index j such that is an edge. By the definition of the tournament, one of the two edge 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 .

Easy to see that algorithm runs in time as we need to search vertex to extend the path and repeat it till we have covered all vertices.

–Saurabh Joshi

### Like this:

Like Loading...

*Related*

Tags: algorithm, graph theory, hamiltonian path, math, theorem, tournament

This entry was posted on November 11, 2010 at 1:00 pm and is filed under algorithm, math, theorem. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

January 11, 2014 at 9:39 am |

Can we do it faster in terms of the number of look-ups in the adjacency matrix?

May 1, 2014 at 12:49 pm |

I think the puzzle was to come up with a poly-time algorithm. Even if you do some nice tricks with adjacency matrix, it is still going to remain poly-time. It would be interesting to see what would be the lowerbound for this problem though.