2
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ Are you familiar with Eulerian graphs? $\endgroup$
    – Pål GD
    Mar 29 at 17:21
  • 2
    $\begingroup$ It’s simpler to reduce from Hamiltonian path. Create multiple copies of the graph and connect them through one vertex. $\endgroup$
    – user114966
    Mar 29 at 17:36
  • $\begingroup$ @Dmitry agreed; "multiple copies" can be $2$ copies. It doesn't even need to be the corresponding vertex in both copies that is identified. $\endgroup$
    – Joffan
    Mar 29 at 18:24
  • $\begingroup$ @Pål GD yes I am familiar with Eulerian Graphs. $\endgroup$ Mar 30 at 1:36
  • $\begingroup$ @Joffan. I am a bit unclear about how the construction works. Assume that the G is a graph with 3 vertices forming a straight line. This graph has an Hamiltonian Path. Now as per the mentioned construction I will create another copy of it and add one vertex and connect that vertex to one endpoint of both straight line graphs. The resulting graph G' is again a straight line graph but with 7 vertices now. I don't see G' having an relaxed-Hamiltonian cycle because more than one vertex will be repeated to visit all vertices. Please clarify. $\endgroup$ Mar 30 at 1:45
2
$\begingroup$

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.

enter image description here

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

$\endgroup$
3
  • $\begingroup$ I will go through your answer. Actually I have another solution. Reduce from Hamiltonian Path. Construct a star S4 graph and connect two of it's corners to all vertices in G(i.e. each of the two vertices is connected to each vertex in G by an edge each total 2|V| edges added), this the graph constructed is G'. Now G has Hamiltonian Path iff G' had Ultra-Hamiltonian cycle. What do you think? $\endgroup$ Mar 31 at 16:03
  • $\begingroup$ Doesn't that construction of $G'$ leave it with two degree-one vertices (from the $S_4$)? which would imply no relaxed-Hamiltonian cycle. Still I'll think about variations on that idea. $\endgroup$
    – Joffan
    Mar 31 at 16:23
  • $\begingroup$ Or maybe you meant the cycle graph $C_4$. In that case I think you run into problems in that one of the attachment nodes can be the nexus for multiple independent disjoint cycles into $G$ (which is what I was avoiding with the limits on forming $w$ above, although I actually have another way to do that). If you ask another question I could describe more fully. $\endgroup$
    – Joffan
    Mar 31 at 16:34
-1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Please use MathJax for mathematic formulae (cs.stackexchange.com/editing-help#latex). Also try to add some structure to your answer and cut it into paragraphs, otherwise it is very difficult to read. $\endgroup$
    – Nathaniel
    Apr 6 at 15:00

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.