• 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!
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).