# 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.

Thanks in advacnce!

• Welcome to MSE. It is in your best interest that you use MathJax. – José Carlos Santos Jun 9 '18 at 13:05

## 1 Answer

Yes, the problem of finding an alternating Hamiltonian cycle with respect a subset of all vertices (the alternating hamiltonian cycle problem) is a NP-complete problem.

To prove, let us reduce the directed Hamiltonian cycle problem, one of Karp's 21 NP-complete problems, to the current problem by a polynomial-time reduction.

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.

(In fact, the problem of finding an alternating Hamiltonian cycle is none other than the problem of finding a Hamiltonian cycle in a bipartite graph. My proof just follows the question 4 of an exercise).