Just want to verify that I have the right idea here with this hamiltonian cycle question.
$HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there is a simple cycle (no vertex repeats) C in the graph that contains all vertices $\}$
$2HC$ = $\{\langle G \rangle$ | $G=(V,E)$ is an undirected graph such that there are two simple cycles $C_1$ and $C_2$ such that atleast one of the cycles contains every vertex $\}$
Using the fact that $HC$ is NP-complete, we wish to prove that $2HC$ is NP-complete.
a) Prove that $2HC \in NP$
My actual written proof is a bit too lengthy so I will just summarize the idea. We know $HC$ is NP-complete and therefore has a polynomial time verifier $V$ that can check for a cycle including all vertices. We can use this verifier to verify $2HC$ but we know that $2HC$ can contain a cycle that does not include all vertices. So we need a second verifier $V'$ that needs to only check for cycles but not ones that include all vertices. There are 3 cases to consider:
- If $V$ accepts both cycles in $2HC$, accept and no need to run $V'$
- If $V$ accepts only $C_1$, run $V'$ on $C_2$ to check if its a cycle, if $V'$ accepts, accept.
- If $V$ accepts only $C_2$, run $V'$ on $C_1$ to check if its a cycle, if $V'$ accepts, accept.
Thus $2HC$ can be verified in polynomial time since both $V$ and $V'$ run in polynomial time so $2HC \in NP$.
b) Prove that $2HC$ is NP-hard by showing that $HC \le_p 2HC$
We already know that $HC$ contains a cycle with all vertices. To reduce $HC$ to $2HC$ we need to introduce a new vertex $v'$ that will connect to 2 vertices $u,w \in G$ such that $u \neq w$. Notice that this will create a second cycle. Since we can easily create a function that adds the new vertex along with the additional 2 edges, the function takes polynomial time and so we have $HC \le_p 2HC$.
Since $2HC \in NP$ and $HC \le_p 2HC$, we can conclude that $2HC$ is NP-Complete.
Your proof of (a) is much more complex than it needs to be. Instead of reducing to a known problem you can just say it directly: 2HC is in NP because it is solved by the nondeterministic machine that guesses two cycles and then checks that they are in fact cycles and contain all vertices between them, and all this is easy to do in polynomial time.
For (b) you have the right general idea, but the execution seems to be slightly flawed. Introducing just one new vertex with edges to existing vertices will not guarantee that the new vertex is the only vertex that benefits from the new cycle. For example, consider the graph
If you add a new vertex connected to 4 and 5, the new graph will be in 2HC even though the original graph is not Hamiltonian.
Instead, just introduce an entire new cycle -- three new vertices with three new edges between them, and not connected to the existing graph.