I'm struggling to understand how to express the recurrence relation in terms of N of a backtracking algorithm to find out if a Hamiltonian path exists. Where N is the number of vectors.

After finding this I then need to find the worst case time complexity of the algorithm.

The algorithm is recursive, and works like so:

$ \text{Function isHamiltonian} (G , v)\\ ~~\text{Input : }G := \{{V, E}\} \\ ~~~~~~~~~~~~~~~~~~~~where\ V\ :=\ \{{v_0, v_1, v_2, ..., v_n}\}\text { (set of vectors)}\\ ~~~~~~~~~~~~~~~~~~~~where\ E\ :=\ V\ \times\ V\ \text{(set of edges expressed as }(v_0, v_1)\ (v_0\ \text{goes to } v_1)\\ ~~~~~~~~~~~~~~~~v \in V\ \text{(starting vertex)}\\ \\ ~~\text{Algorithm}\\ ~~~~Let\ H:=\{{V', E}\}\ where\ V' = V\ \backslash\ v\\ ~~~~\text{if}\ V' = \emptyset\\ ~~~~~~~~\text{return true (There is a path)}\\ ~~~~\text{for all}\ w \in V' : (v,\ w)\ \in E\\ ~~~~~~~~\text{if isHamiltonian}(H,\ w)\text{ is true}\\ ~~~~~~~~~~~~\text{return true}\\ ~~~~\text{return false} $

My problem is that I thought that the recurrence relation would vary with the number of edges, not just the number of vertices?

Also, I understand that the worst case is that the algorithm has to check every possible permutation $(n!)$, or here $(n-1!)$ (as the first vertex is preselected). So I thought that the worst case would be when there are the maximum number of permutations without having any possible paths (or a unique path). I just can't understand the conditions that reliably define a worst case graph. (Such as a strongly connected graph with the exception of one isolated point).

Any help you could give me would be very helpful. I've tried a lot of searching but most material deals with more complex algorithms than exhaustive search.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.