Ultra-Hamiltonian cycle

Question

Ultra-Hamiltonian cycling is defined to be a closed walk that visits every vertex exactly once, except for at most one vertex that visits more than once.

Question:- Prove that it is NP-hard to determine whether a given graph contains an ultra-Hamiltonian cycle.

We can reduce it from the Hamiltonian cycle problem which is a NP-hard problem but I'm not getting from where to start for reducing it to the ultra-hamiltonian cycle problem.

Can you tell me the approach to do it?

Answer 1

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.