graphshortest-pathnpnp-hardhamiltonian-cycle

Shortest Path from Node A to B by going through all other Nodes (NP-Hard?)


My problem: Find the shortest path from node A to node B that passes through all other nodes of the unweighted, direct graph. I know that there exists such a path.

I believe this is NP-Hard, but I can't explain it. My Prof. likes to have the algorithm perform on a runtime of O(|V| + |E|), where V is the set of nodes and E the set of edges.

It seems it is similar to this problem, but the Graph's properties are different, does it make a difference?


Solution

  • Yes it's NP-hard. If your solver ran in P, then by running it on every pair of points you'd have a P-time solver for Hamiltonian Path.

    The answer you linked gives a more rigorous proof.