0
$\begingroup$

Problem : Let $G$ be a weighted complete graph with a non-negative weight function w. For fixed vertices $u, v \in V (G)$, where $u \neq v$ we would like to find a minimum Hamilton path from $u$ to $v$. Explain how to convert this problem to the problem of a minimum Hamilton cycle in an appropriate graph $G^∗$.

Thoughts:

I have seen this idea for showing a ham path exists if a ham cycle exists : Modify your graph by adding another node that has edges to all the nodes in the original graph.

If the original graph has a Hamiltonian Path, the new graph will have a Hamiltonian Circuit: the circuit will run from the new node to the start node of the Path, through all the nodes along the Path, back to the new node.

But I am unsure for how to make this work for weight functions, and moreover for 2 specific vertices. Hints much appreciated.

As an aside, is it true that there will always exist a hamiltonian path with every pair of fixed starting and ending vertices in a complete graph?

$\endgroup$
  • 2
    $\begingroup$ Couldn't you add a node connected to $u$ and to $v$ with those two edges being given weight zero and with no other new edges? (Maybe that only gives a minimum Hamiltonian cycle from $u$ to $u$, not in general, so maybe I don't understand the problem...) $\endgroup$ – Ian Mar 16 '17 at 1:09
  • 2
    $\begingroup$ If you have a new node $x$ that is adjacent to every other node, then the minimum cycle might be $v\rightarrow$(a bunch of vertices)$\rightarrow u\rightarrow$ (a bunch of vertices, including $x$)$\rightarrow v$. If you cut out $x$, you don't necessarily have a path from $u$ to $v$. So you need to make sure that if you have a minimal cycle and cut out $x$, that the remaining path goes from $u$ to $v$. Do you see how Ian's solution accomplishes this? I don't think the weights need to be 0, or even any specific value. $\endgroup$ – Sam Jaques Mar 16 '17 at 2:28
  • $\begingroup$ @SamJaques the graph is complete. There will always be a u-v path. $\endgroup$ – IntegrateThis Mar 16 '17 at 12:48
  • $\begingroup$ @Ian I think your answer is correct. You can post it as an answer and I will accept it if you like. Although I am not 100% sure to be honest. $\endgroup$ – IntegrateThis Mar 16 '17 at 12:57
  • 1
    $\begingroup$ Sorry, I wasn't quite clear. Suppose I have a complete graph on four vertices $\{u,v,w,z\}$. If I add a vertex $x$, adjacent to all fourvertices, then run some algorithm to find a minimal ham cycle, I might get $(u,x,w,v,z)$. Then if I cut out the new vertex $x$, to find a minimal ham path in the original graph, I only have a ham path $(w,v,z,u)$ that goes from $w$ to $u$, not $v$ to $u$. There will be other ham paths from $u$ to $v$, but I have no guarantee that they are minimal. $\endgroup$ – Sam Jaques Mar 17 '17 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.