GATE CS 2006 Q31 — Regular and Context-free Languages

To determine the complexity of $\text{DHAM}_3$ and $\text{SHAM}_3$, we can relate them to the standard Hamiltonian Cycle (HC) problem, which is known to be NP-complete.

1. Analyzing $\text{DHAM}_3$ (Decision Version)

We can show that the standard Hamiltonian Cycle problem reduces to $\text{DHAM}_3$ in polynomial time ($HC \le_P \text{DHAM}_3$):

• Given an arbitrary graph $G = (V, E)$, we construct a new graph $G' = (V', E')$ by replacing each vertex $v \in V$ with a path of $3$ vertices: $v_1 - v_2 - v_3$.
• For every edge $(u, v) \in E$, we add edges in $G'$ connecting the endpoints of their respective paths (e.g., $(u_3, v_1)$ and $(v_3, u_1)$).
• The number of vertices in $G'$ is $|V'| = 3|V|$, which is guaranteed to be divisible by $3$.
• Any Hamiltonian cycle in $G'$ must traverse the vertices of each gadget $v_1 - v_2 - v_3$ consecutively. Thus, $G'$ contains a Hamiltonian cycle if and only if $G$ contains a Hamiltonian cycle.

Since this reduction is polynomial-time, and the general Hamiltonian Cycle problem is NP-complete, the restricted decision problem $\text{DHAM}_3$ is NP-hard.

2. Analyzing $\text{SHAM}_3$ (Search Version)

The search version of a problem is always at least as hard as its decision version. If we had a polynomial-time algorithm to find a Hamiltonian cycle ($\text{SHAM}_3$), we could use it to decide if one exists ($\text{DHAM}_3$) in polynomial time.

Since $\text{DHAM}_3$ is NP-hard, the search problem $\text{SHAM}_3$ must also be NP-hard.

Therefore, both $\text{DHAM}_3$ and $\text{SHAM}_3$ are NP-hard.