# Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$

Say I have an undirected, weighted graph $G=(V,E)$ and I know a hamiltonian cycle of minimum weight in that graph. Can I use that information to efficiently find a hamiltonian cycle in $G'=(V',E')$ where $V'=V-\{v\}$ for some vertex $v$ and $E'$ is $E$ with all edges touching $v$ removed?

It is safe to assume that there still exists a hamiltonian cycle in $G'$.

• What is the point of the weights? Also, you need more assumptions. There exists $G$ for which $G'$ is not Hamiltonian. – Tyson Williams May 13 '13 at 22:37
• Looking for the lowest cost Hamiltonian cycle. It is safe to assume that there will be a Hamiltonian cycle in $G'$. – mikeazo May 13 '13 at 23:39
• If weighted graph is nonstandard for Hamiltonian cycle, then it is okay to assume unweighted. – mikeazo May 13 '13 at 23:43
• Related note: Finding a second Hamiltonian cycle in a 3-regular graph (without removing a vertex) is in Papadimitrious' class PPA. – Martin Schwarz May 14 '13 at 12:22

Assume that I can efficiently find a hamiltonian cycle of minimum weight in $G'$ given a hamiltonian cycle of minimum weight in $G$. I can use this procedure to find a hamiltonian cycle in any graph, say $A$.
The procedure would work like this. Take $A$ and add vertices and edges (with weight $0$) such that a hamiltonian cycle of weight $0$ is easy to find. The cycle, for example, could alternate between new vertices and the original vertices of $A$. Since all new edges have weight $0$, the cycle weight would be $0$. If we call the new graph $A_1$, we know a simple hamiltonian cycle in $A_1$. Remove one of the newly added vertices from $A_1$ to create $A_2$ then run our procedure to efficiently find a hamiltonian cycle in $A_2$. Then repeat the procedure.
Eventually we will arrive at a graph, say $A_k$, which only has one extra vertex when compared to $A$. We will know a hamiltonian cycle in $A_k$ from the procedure above. So we can use this information to efficiently find a hamiltonian cycle in $A$ (using the same procedure as above).
Therefore, finding a hamiltonian cycle in $G'$ given one in $G$ must be at least as hard as finding a hamiltonian cycle in general.