Determine if a Hamiltonian Cycle exists?

Question

Suppose I have a graph $G=(V, E)$. Removing a subset $R$ of edges from $G$ results in a new graph $G^\prime=(V, E\setminus R)$. The maximum number of edges in $R$ is $|E|$. Suppose I have the graph $G^\prime$ and I know it is a 2-regular graph with multiple (disconnected) cycles. Additionally, suppose the set $R$ is given. I was wondering, based on those conditions, if it is possible to determine if $G$ has a Hamiltonian Cycle in polynomial time?

Answer 1

No.

You could reduce the problem of finding a Ham cycle in a graph, for any graph, to this problem. Indeed, let $H$ be the graph you want to see if there is a Ham cycle in. Replace each vertex $v$ with a cycle $C_v$ of your favourite length--as long as it is no larger than polynomial in $H$ that is, and if $uv$ is an edge in $H$ then put a complete bipartite graph between the vertices of $C_u$ and $C_v$.

Then the resulting graph $G$ has a hamiltonian cycle iff $H$ does. Furthermore, from this construction of $G$ you automatically have your set $R$ of edges; indeed the edges in $G$ between $C_u$ and $C_v$; $u$ and $v$ adjacent in $H$.