# Alternating hamiltonian cycles is in NP-complete

• Alternating-Hamiltonian-Cycle: Given a graph G = (V, E), and a subset A ⊆ V of its vertices, does there exist a Hamiltonian Cycle of G, such that the cycle alternates between vertices in A and vertices in V \ A?

For example, if V = {a1, a2, a3, b1, b2, b3} and A = {a1, a2, a3}, and there were edges between every vertex, then the answer would be YES, because {a1, b1, a2, b2, a3, b3, a1} is both a Hamiltonian cycle and alternates between vertices in A and vertices not in A.

For some questions like above, how can we prove that alternating hamiltonian cycle is in NP-complete?

I could prove that it is in NP, but do not know how to reduce problem from NP-hard...

I am confused about the word "Alternating" Hamiltonial cycle.

Let $G$ be an directed graph with vertices $V$. For each vertex $u$ in $G$, we create four new vertices, $u_{in}, u_{left},u_{right}, u_{out}$ and three undirected edges $(u_{in},u_{left}),(u_{left},u_{right}),(u_{right}, u_{out})$. For each directed edge $(u, v)$ is in $G$, we create an undirected edge $(u_{out},v_{in})$. Let $G'$ be the graph with all created vertices and edges. Consider the subset of all vertices $A$ which consists of all vertices $u_{out}$ and $u_{right}$ for $u\in G$. It is not hard to see that Hamiltonian cycles in $G$ are in one-to-one correspondence with alternating Hamiltonian cycles in $G'$ with respect to subset $A$. So we have reduced the directed Hamiltonian cycle problem to the alternating Hamiltonian cycle problem. We can see easily that this reduction is a polynomial-time reduction.