Prove that the language HAMTWOCYCLES = {G | there exist two cycles in G such that any vertex belongs to exactly one of them} is NP-complete

Question

I have attempted to prove this theorem, but I am not confident in my solution. Can someone please review my proof and let me know if there are any errors, or provide a correct proof if mine is incorrect?

To prove that HAMTWOCYCLES is an NP-complete problem, we need to show that it is both in NP and NP-hard.

• First, we show that HAMTWOCYCLES is in NP.

Given a graph G and two cycles C1 and C2 in G, we can easily verify that every vertex in G belongs to exactly one of C1 and C2 in polynomial time. To do so, we can check that every vertex in G is included in exactly one of the cycles C1 and C2, and that the cycles are indeed cycles (i.e., they do not contain any repeated vertices and each vertex has exactly two incident edges in the cycle). Since the verification can be done in polynomial time, HAMTWOCYCLES is in NP.

• Next, we show that HAMTWOCYCLES is NP-hard by reducing the problem of determining whether a graph contains a Hamiltonian cycle (which is known to be NP-complete) to HAMTWOCYCLES.

Let G be a graph, and let G’ be the graph obtained by adding a new vertex v to G and connecting it to every vertex in G. Then, we claim that G contains a Hamiltonian cycle if and only if G’ belongs to HAMTWOCYCLES.

To see why, suppose that G contains a Hamiltonian cycle C. Then, we can construct two cycles C1 and C2 in G’ as follows: let C1 be the cycle obtained by replacing v in C with the path that connects v to the two vertices in G that are adjacent to v, and let C2 be the remaining cycle in G’ that includes all the other vertices in G’. It is easy to see that every vertex in G’ belongs to exactly one of C1 and C2, since v is included only in C1 and all other vertices are included only in C2. Moreover, C1 and C2 are both cycles, since C1 includes the two edges that connect v to G and C2 is a Hamiltonian cycle in G. Therefore, G’ belongs to HAMTWOCYCLES.

Conversely, suppose that G’ belongs to HAMTWOCYCLES, and let C1 and C2 be the two cycles in G’ such that every vertex in G’ belongs to exactly one of them. Since v is included only in C1, C1 must contain all the edges incident to v. Let C2’ be the cycle obtained by removing v from C2. Then, C2’ is a Hamiltonian cycle in G, since it includes all the vertices in G. Therefore, G contains a Hamiltonian cycle.

Since we have shown that the problem of determining whether a graph contains a Hamiltonian cycle reduces to the problem of determining whether a graph belongs to HAMTWOCYCLES, and since the former problem is known to be NP-complete, the latter problem is also NP-complete.

Answer 1

Great structure, but v alone may not be enough for a Polynomial reduction.

A language L is NP-complete if it is in NP and it is NP-hard.

• L is in NP, if and only if (iff) it's polynomially verifiable.

Same as yours, could be verified in polynomial time $O(V)$, where V is the number of vertices.

• L is NP-hard, iff for every language A ∈ NP, $A ≤_P L$. (A is polynomial time reducible to L)

Same idea of reducing the problem of determining whether a graph contains a Hamiltonian cycle (which is known to be NP-complete) to HAMTWOCYCLES.

For any language A in NP, that $A≤_P 3SAT$.

$3SAT ≤_P$ Hamiltonian cycle. [Classical conclusion]

Now Require to Prove, Hamiltonian cycle $≤_P$ HAMTWOCYCLES.

Let $G = (V, E)$, and let $f(G)=G’$ be the graph obtained by adding two new vertices v and v' to G and connecting them to every original vertex in G. Then, we claim that G contains a Hamiltonian cycle if and only if G’ belongs to HAMTWOCYCLES. [so that the v' is not reused in the second cycle C2, but v instead.]

Suppose that G contains a Hamiltonian cycle C. Then, we can construct two cycles C1 and C2 in G’ as follows: let C2 be the cycle obtained by replacing v in C with the path that connects v to the two vertices in G that are adjacent to v, and let C1 be the remaining cycle in G’ that includes all the other vertices in G’. $f(G)=G’$ exists two cycles, which satisfies HAMTWOCYCLES.

Conversely, suppose that $f(G)=G’$ belongs to HAMTWOCYCLES. Let C1 and C2 be the two cycles in G’ such that every vertex in G’ belongs to exactly one of them. In which case, it must be of two cycles C1:(v1, v), ′, (v4, v); C2: (v2, v'), (v', v3), (v3, v2). But then, G contains a Hamiltonian cycle (v2, v1), ′, (v4, v3), (v3, v2).

By the transitivity of reducibility, for any language A in NP, $A ≤_P$ HAMTWOCYCLES.

It immediately follows that HAMTWOCYCLES is NP-complete.

Reference: Hamiltonian-Cycle-to-Hamiltonian-Path