Tournament graph and Hamiltonian Path

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

Advertisements

Tags: , , , , ,

2 Responses to “Tournament graph and Hamiltonian Path”

  1. anonymous Says:

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

    • Saurabh Joshi Says:

      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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: