Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question
    
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

1 Answer 1

up vote 0 down vote accepted

I'm pretty sure my proof works, but I didn't formalize it so I'm not sure. It indeed uses the same argument as the lower bound for comparison based sorts (if you don't know it then I doubt it's the solution your professor/textbook expects).

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)

share|improve this answer
    
Seems legit. You really helped me, gave some ideas, thank you! –  xan Nov 6 '12 at 20:44

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.