0
$\begingroup$

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.