Proving NP-hardness of Hamiltonian Cycle problem variant

Question

I need to prove that determining whether a graph has a relaxed-Hamiltonian cycle (definition given ahead) is NP-hard.

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of $G$ exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated twice or even more times).

Note: In a closed walk we can visit a vertex or edge multiple times, but first and last vertex are same. In the relaxed-Hamiltonian cycle this first and last vertex being the same is not counted as repetition.

I am thinking reducing to relaxed-Hamiltonian cycle from Hamiltonian Cycle.

Claim: Construct graph $G'$ given $G$ such that $G$ has Hamiltonian cycle iff $G'$ had relaxed-Hamiltonian cycle.

My idea is that if a graph $G$ has one or more articulation points then it cannot have a Hamiltonian Cycle so simply give a $G'$ which does not have a relaxed-Hamiltonian cycle.

The problem is when graph $G$ does not have any articulation points. In this case the graph $G$ may or may not have an Hamiltonian Cycle. I cannot think of a construction for this case such that my claim holds.

Is my approach correct? If yes please suggest how I could take care of the mentioned case? Otherwise, please hint me towards the correct direction of thinking to get the right construction.

Answer 1

Your definition:

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of G exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated 2 or even more times).

I'll call this revisited vertex (for a given $C$) the nexus of $C$ and look at a case that shows that even if we know which node must be the nexus of any relaxed-Hamiltonian cycle, the problem is still NP-hard.

Consider two graphs $G_1,G_2$ for which finding a Hamiltonian cycle is NP-hard (which may be two copies of the same graph). Then we create $G$ by identifying a vertex in $G_1$ with a vertex in $G_2$, with the single vertex thus created called $w$. $w$ is an articulation vertex so $G$ cannot have a (standard) Hamiltonian cycle.

If a relaxed Hamiltonian cycle exists in $G$, it must have $w$ as its nexus. To visit all nodes in $G$, we have to visit $w$ and that is the only node which allows us to cross into $G_2$ and visit all nodes there. So we have the second (minimum) visit and $w$ is the nexus.

The definition of the relaxed Hamiltonian cycle means that we could in principle find disjoint cycles all including $w$ within either $G_1$ or $G_2$ and still meet the relaxed-Hamiltonian standard. We can avoid this case by ensuring that nodes in $G_1$ and $G_2$ that we pick for identification to create $w$ are maximum degree $3$, so we cannot re-enter a second cycle in the same graph part from $w$.

Then the problem of finding a relaxed Hamiltonian cycle in $G$ is as hard as finding Hamiltonian cycles in both $G_1$ and $G_2$ which we know can be NP-hard.

Further to your claim, we therefore know that if we find a relaxed Hamiltonian cycle for $G$ we have found a Hamiltonian cycle for both $G_1$ and $G_2$ (and $G_2$ is allowed to be a copy of $G_1$).

Answer 2

Here we will refer relaxed- Hamiltonian cycle as Ultra-Hamiltonian cycle. We know Hamiltonian-Path problem is known to be in NP-complete, Now to prove that ultra-Hamiltonian Cycle is NP-hard we will reduce Hamiltonian-Path problem to ultra Hamiltonian Cycle problem. To prove: Hamiltonian Path ≤P ultra-Hamiltonian Cycle Proof:For every instance of the Hamiltonian Path problem consisting of a graph G =(V, E) as the input can be converted to ultra-Hamiltonian Cycle problem consisting of graph G’ = (V’, E’). We will construct the graph G’ in the following way: V’ = Add vertices V of the original graph G and add 5-additional vertex V0 V1 V2 V3 V4 in butterfly formation(Explained below), such that each and every vertex of the original graph G are connected to vertices V3 and V4. Here in Graph G’ The number of vertices increases by 5, V’ =V+5. E’ = Add edges E of the original graph G and add new edges between the newly added vertices V3 and V4 to the all original vertices of the graph G. In G’ The number of edges increases by the number of vertices 2V. These 5 added vertices (V0 V1 V2 V3 V4) are in a butterfly graph with V0 as articulation point The new graph G’ can be obtained in polynomial time. The validation of reduction can be proved by the following two claims: i)(Forward Direction) Let us assume that the graph G contains a hamiltonian path covering the V vertices of the graph starting at a random vertex say Vstart and ending at Vend, now since we connected all the vertices to two new vertices V3 and V4 in G’. We extend the original Hamiltonian Path to a ultra-Hamiltonian Cycle by using the edges Vend to V3 and V4 to Vstart respectively. The graph G’ now contains the cycle traversing all vertices exactly once except V0 (articulation point in butterfly graph) which is visited more than once, this traversal start from V0 to V1 to V2 to V0 to V4 to Vstart to ”hamiltonian path in G” to Vend to V3 to V0. (Here V0 V1 V2 V3 V4 are of butterfly graph). So this is ultra-hamiltonian path in G’. . ii)(backward Direction) We assume that the graph G’ has a ultra-Hamiltonian Cycle passing through all the vertices, inclusive of V0 V1 V2 V3 V4, as V0 is an articulation point so it must be visited more than once and no other vertex is visited more than once, also the path from Graph G can enter the Butterfly graph either at V3 or V4 and leave the butterfly graph at V3 or V4(whichever is not used for entering in butterfly graph). Once the path leave the butterfly-graph it will visit each vertices of Graph G in path and comeback to butterfly graph(never to go back to vertex of graph G). This path must use one of V3 and V4 for exit and other for entry from Butterfly graph to vertices of Graph G (Ad V0 is articulation point and is already being visted more than once, so no other vertex can be visited more than once). Now to convert it to a Hamiltonian Path, we remove all the edges corresponding to the vertex V0 V1 V2 V3 V4 in the cycle. The resultant path will cover the vertices V of the graph and will cover them exactly once. So here we get hamiltonian path in G, from ultra-Hamiltonian cycle in G’ Thus we can say that the graph G’ contains a ultra-Hamiltonian Cycle if and only if graph G contains a Hamiltonian Path. Therefore, any instance of the ultra-Hamiltonian Cycle problem can be reduced to an instance of the Hamiltonian Path problem. Thus, the ultra-Hamiltonian Cycle is NP-Hard.