Using Traveling Salesman Solver to Decide Hamiltonian Path

Question

This is for a project where I'm asked to implement a heuristic for the traveling salesman optimization problem and also the Hamiltonian path or cycle decision problem. I don't need help with the implementation itself, but have a question on the direction I'm going in.

I already have a TSP heuristic based on a genetic algorithm: it assumes a complete graph, starts with a set of random solutions as a population, and works to improve the population for a number of generations. Can I also use it to solve the Hamiltonian path or cycle problems? Instead of optimizing to get the shortest path, I just want to check if there is a path.

Now any complete graph will have a Hamiltonian path in it, so the TSP heuristic would have to be extended to any graph. This could be done by setting the edges to some infinity value if there is no path between two cities, and returning the first path that is a valid Hamiltonian path.

Is that the right way to approach it? Or should I use a different heuristic for Hamiltonian path? My main concern is whether it's a viable approach since I can be somewhat sure that TSP optimization works (because you start with solutions and improve them) but not if a Hamiltonian path decider would find any path in a fixed number of generations.

I assume the best approach would be to test it myself, but I'm constrained by time and thought I'd ask before going down this route... (I could find a different heuristic for Hamiltonian path instead)

Answer 1

Both are NP complete problems, so by definition you can convert the input and use the same algorithm ;-)

But the basic idea should work. Of course you may need to change the generation of new paths and the success criteria.

EDIT: BTW: There is a suggestion for a randomized algorithm: http://en.wikipedia.org/wiki/Hamiltonian_path_problem

Answer 2

Don't know if you ever got an answer to this. The simple trick is to add one dummy point that has a distance of zero to all your other points. Solve the TSP and get rid of the dummy point - what remains is the Hamiltonian Path. Simple !