<p>I believe the answer is no and here is why.</p>

<p>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$.</p>

<p>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. </p>

<p>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).</p>

<p>Therefore, finding a hamiltonian cycle in $G'$ given one in $G$ must be at least as hard as finding a hamiltonian cycle in general.</p>

CC BY-SA 3.0
2013-05-14T12:20:22.970Z
2013-05-14T12:43:17.663Z
2013-05-14T12:43:17.663Z
mikeazo
<p>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?</p>

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

CC BY-SA 3.0
2013-05-13T22:37:22.293Z
What is the point of the weights? Also, you need more assumptions.  There exists $G$ for which $G'$ is not Hamiltonian.
Tyson Williams
CC BY-SA 3.0
2013-05-13T23:39:01.427Z
Looking for the lowest cost Hamiltonian cycle. It is safe to assume that there will be a Hamiltonian cycle in $G'$.
mikeazo
CC BY-SA 3.0
2013-05-13T23:43:19.113Z
If weighted graph is nonstandard for Hamiltonian cycle, then it is okay to assume unweighted.
mikeazo
CC BY-SA 3.0
2013-05-14T12:22:49.750Z
Related note: Finding a second Hamiltonian cycle in a 3-regular graph (without removing a vertex) is in Papadimitrious' class PPA.
Martin Schwarz
<cc.complexity-theory><graph-theory><hamiltonian-paths>
Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$
mikeazo
# Finding a hamiltonian cycle in $G'$ given a hamiltonian cycle in $G$

(Asked by: username_0 on 2013-05-13)

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'$.

**Tags:** cc.complexity-theory, graph-theory, hamiltonian-paths

> **Comments:**
> **username_1**: What is the point of the weights? Also, you need more assumptions.  There exists $G$ for which $G'$ is not Hamiltonian.  
> **username_0**: Looking for the lowest cost Hamiltonian cycle. It is safe to assume that there will be a Hamiltonian cycle in $G'$.  
> **username_0**: If weighted graph is nonstandard for Hamiltonian cycle, then it is okay to assume unweighted.  
> **username_2**: Related note: Finding a second Hamiltonian cycle in a 3-regular graph (without removing a vertex) is in Papadimitrious' class PPA.  

---

## 1 answers

### Answer by username_0 on 2013-05-14. Score: 2 | Accepted answer

I believe the answer is no and here is why.

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.


---

