Solving an extension of the Shortest Hamiltonian Path

Question

I was thinking about an extension to the Shortest Hamiltonian Path (SHP) problem, and I couldn't find a way of solving it. I know it is NP-complete, but I figured I'd ask here for ideas, since I do not want to simply brute force the problem.

The extension is fairly simply: Given an undirected, complete, weighted graph with n vertices, find the shortest hamiltonian path with end vertices v and u.

So, bruteforce would still take O(n!) time, since the remaining n-2 vertices can be visited in (n-2)! ways. I was trying to find a way to maybe solve this slightly faster. My efforts for finding a way to solve this problem in a beneficial manner has so far been fruitless.

Would anyone have an idea how to exploit the knowledge of the end-vertices? Preferably explained alongside some pseudocode. It is required for the solution found to be optimal.

I guess it could be solved by integer programming, since the knowledge of end nodes are fairly limiting, and makes it easy to avoid cycles, but it wouldn't really exploit the composition of the problem.

Answer 1

If you want to find the shortest path to connect all nodes, then you should look at travelling salesman algorithms. I don't exactly see why you approach it as an HSP. The only reason I can think of is that you want to specify your starting cities, but it should be easy to fix that (if you need that I can post it) by changing your graph a bit.

edit: adding how to tweak your graph

Add 1 node (call it E) and only connect it to your starting and ending nodes. A TSP will compute a solution to your problem by connecting all your nodes. As E is only reachable by going from start to E and then to end, the solution (a cycle yes) will contain start - E - end. Then you remove the 2 edges to and from E and you have the optimal solution. Within the TSP, the path from start to end will be optimal.

Answer 2

You can use a metaheuristic algorithm. There are many kinds of them (Local search, constructive search, etc.). One of them could be based on:

For each x belonging to the set of vertices X:
- Find the set of closest vertices to x C.
- Filter the set C in order to include one of them in the path P.
Repeat until all vertices of X have been included in the path P.
End.