Is it possible to use Dijkstra's Shortest Path Algorithm to find the shortest Hamiltonian path? (in Polynomial Time)

2
votes

I've read that the problem of finding whether a Hamiltonian path exists in a graph is NP-Complete, and since Dijkstra's Shortest Path Algorithm runs in Polynomial Time, it cannot be modified to find the shortest Hamiltonian path. (Is this logic valid?)

But what if you are given two nodes (say A and Z) on an undirected graph (with all edges having non-negative costs), and it is given that there is at least one Hamiltonian path with the given nodes (A and Z) as end points. Given these specifications, would it now be possible to modify Dijkstra's algorithm to find the shortest Hamiltonian path with A and Z as endpoints? (in Polynomial Time)

Note: I'm only concerned with finding the shortest Hamiltonian path from two nodes specifically. For example, if there is a graph containing 26 nodes (labelled A to Z), what is the shortest path that passes through all points but starts at A and ends at Z. (I'm not concerned with finding other Hamiltonian paths with different endpoints, just A and Z)

Additional question: If the answer is "No" but there is another algorithm that can be used to solve this, what algorithm is it, and what is its time complexity?

(Note: This question has "hamiltonian-cycle" as a tag, even though I'm looking for a Hamiltonian PATH, because I do not have enough rep to make the tag "hamiltonian-path". However, let's say A and Z is connected by exactly one edge, then the shortest Hamiltonian path can be found by finding the shortest Hamiltonian cycle and then removing the edge connecting A and Z)

2
algorithmgraph-theorydijkstranp-completehamiltonian-cycle
You can use anything to solve anything; it's just that in this case you can't have a polynomial time reduction - user2134086
In your first sentence: if "do P and NP coincide?" can be answered with "yes", then your logic is valid. - user824425
There are many NP problems that can be solved in polynomial times when some special condition applies in the problem. This is because sometimes, NP problems are NP problems on their most generic field of application. But when you start to put hypothesis, there can be simplifications. You have multiple "given" in your question, so you stand a chance. - v.oddou
This question appears to be off-topic because it is about graph theory. It is an interesting question, but I think it would be better suited for math.stackexchange.com - Barranka
Might also be a better fit at Theoretical Computer Science. - Brad Koch

2 Answers

1
votes

No, this is not possible. Your simplified problem is still NP-hard. A reduction from travelling salesman:

Given a graph (V, E), find the shortest path that visits each v in V exactly once. Take an arbitrary vertex v in V. Split v into two vertices v_source and v_sink. Use your algorithm to find the shortest hamiltonian path P from v_source to v_sink. P is the shortest cycle starting and ending at v which visits each v in V. Since P is a cycle, the 'starting' vertex is irrelevant. Therefore, P is also the solution to the travelling salesman problem.

The reduction is obviously polynomial time (constant, actually), so your problem is NP-hard.

1
votes

But what if you are given two nodes (say A and Z) on an undirected graph (with all edges having non-negative costs), and it is given that there is at least one Hamiltonian path with the given nodes (A and Z) as end points. Given these specifications, would it now be possible to modify Dijkstra's algorithm to find the shortest Hamiltonian path with A and Z as endpoints? (in Polynomial Time)

How do you propose to modify it? This only works if there is a single path between A and Z and it visits all the other points on the graph. Otherwise, Dijkstra would terminate some shorter path that only visits some subset of the nodes. If there is a Hamiltonian path between A and Z, you could solve the longest path problem, but this is also NP-hard.