2
$\begingroup$

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.

$\endgroup$

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.