0
$\begingroup$

I know that, in general, the Shortest Hamiltonian Path Problem in a general weighted graph is NP-complete. I am wondering, however, if the restriction to a complete weighted graph admits an algorithm in P. Being in a complete graph does give the knowledge that a Hamiltonian path exists in the first place.

My guess is that if such an algorithm exists, it will be some modification of a DFS or potentially modifying a minimal spanning tree in some way to arrive at the solution.

$\endgroup$
4
  • $\begingroup$ What is a "shortest Hamiltonian path"? By definition, all Hamiltionian paths have same length… $\endgroup$
    – Nathaniel
    Dec 2, 2023 at 20:17
  • $\begingroup$ Do you mean Travelling Salesman Problem? $\endgroup$
    – rus9384
    Dec 2, 2023 at 20:23
  • $\begingroup$ No, the shortest Hamiltonian path problem is finding the Hamiltonian path starting at a given vertex in a weighted graph that minimizes the edge weights, it is not Travelling Salesman and not all Hamiltonian paths have the same length in a weighted graph. (Kind of like the shortest path problem in a weighted graph). It is similar to Travelling Salesman though but instead of looking for a Hamiltonian cycle, the problem looks for a Hamiltonian path (i.e. there is no restriction that the path must terminate where it began). $\endgroup$
    – WakkaTrout
    Dec 2, 2023 at 20:31
  • $\begingroup$ Please edit the question to define the problem you are asking about. Don't put clarification in the comments. $\endgroup$
    – D.W.
    Dec 2, 2023 at 20:42

1 Answer 1

0
$\begingroup$

It is NP-hard. It is as hard as the standard Hamiltonian path problem (testing the existence of a Hamiltonian path in an arbitrary graph).

Here is the reduction. Suppose you have an arbitrary graph $G$, with no edge weights/lengths, and we want to know whether it has a Hamiltonian path or not. Treat every edge of $G$ as having length 1. Then, add all missing edges, but with edge length of some huge number (larger than $|V|$, the number of vertices in $G$), so now you have a complete graph. Suppose you had an efficient way to find the shortest Hamiltonian path in any complete graph. Then you could find the shortest Hamiltonian path in this complete graph. If its total length is less than $|V|$, then it is a Hamiltonian path for $G$ (it obviously can't include any of the huge-length edges); if its total length is $\ge |V|$, then $G$ has no Hamiltonian path.

Your problem is almost the same as the Travelling Salesman Problem, but for a path instead of a cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.