CODEWITHSUNDEEP
graph
qbisson
qbisson

Reputation: 185

Hamiltonian path algorithm

I have a project where I have to find, if it exists, an hamiltonian path in a undirected unweighted graph with two different algorithms. I already implemented an heuristic algorithm using backtracking but I've been looking for the other and I can't seem to find it.

So my question is, which algorithm do you know to find an hamiltonian path other than using backtracking?

EDIT : After looking at several other posts, I found that we could find an hamiltonian path by using the longest path algorithm and check if the length of the path equals number of vertex - 1. I'd like to know if this is true or not.

Thanks in advance.

Upvotes: 4

Views: 3063

Answers (1)

ccoakley
ccoakley

Reputation: 3255

Since hamiltonian path is NP-complete, you'll probably end up with some form of backtracking. Whether you use the stack or exhaustive enumeration to achieve your exponential blow up is largely up to you.

If you look for formulations, you can look at various TSP algorithms (I don't really know hamiltonian path techniques). Take into account that any that exploit the triangle inequality won't apply, since your weights are all effectively 1 and infinity (edge does not exist).

Look for branch and cut formulations of TSP that don't require the triangle inequality. Branch and cut seems to be the state of the art technique for provably-optimal solutions to the TSP.

Branch and bound with a minimum spanning tree might be nice (it's easy to implement), and you can augment the minimum spanning tree with node-weights in an iterative fashion (between branching) as a way of breaking nodes of degree > 2 into nodes of degree 2 without changing the correctness of the result. I can't remember the technique name (and I'm at work, so I can't look it up). But your new distance metric for MST would be:

cost[i,j] = (exists(i,j) ? 1 : infinity) + node_augmentation[i] + node_augmentation[j].

The rules for changing augmentation for decent convergence are a little more complicated (increase if degree[i] > 2, decrease if degree[i] < 2), but again, I can't remember the paper (I think it might have been Held-Karp, but I may be way off).

Sorry for a crappy answer, I hope that helps you in your search for approaches, though. Since I don't really know how well TSP techniques apply to hamiltonian path techniques, I may be of no help.

Upvotes: 2

Related Questions