3
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

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

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