Reduction: Rudrata (s,t) Path → Rudrata Cycle

The RUDRATA CYCLE problem: Given a graph, is there a cycle that passes through each vertex exactly once?

RUDRATA $(s,t)$-PATH: Two vertices $s$ and $t$ are specified, we want a path starting at $s$ and ending at $t$ that goes through each vertex exactly once.

Reduction: maps an instance $(G = (V,E), s, t)$ of RUDRATA $(s,t)$- Path into an instance $G’ = (V’, E’)$ of RUDRATA CYCLE as follows: $G’$ is simply $G$ with additional vertex $x$ and 2 additional edges $\{s,x\}, \{x,t\}$.

To recover a Rudrata $(s,t)$-path in $G$ given any Rudrata cycle in $G’$, we simply delete edges $\{s,x\}, \{x,t\}$ from the cycle.

To confirm the validity of this reduction, we show that it works in the case of either outcome depicted:

1. When the instance of RUDRATA CYCLE has a solution
   1. Since the new vertex $x$ has only two neighbors, $\{s, t\}$
      1. any Rudrata cycle in $G’$ must consecutively traverse the edges $\{t,x\}$ and $\{x,s\}$.
   2. The rest of the cycle then traverses every other vertex en route from $s$ to $t$.
   3. Thus deleting the two edges from the Rudrata Cycle gives a Rudrata path from $s$ to $t$ in the original graph $G$.

2. When the instance of RUDRATA CYCLE does not have a solution
   1. We must show that the original instance of RUDRATA $(s,t)$-PATH cannot have a solution either.
      1. Usually easier to prove the contrapositive: If there is a solution of the original problem in $G$, then there is a solution of the problem in $G’$
      2. Just add the two edges $\{t,x\}$ and $\{x,s\}$ to the Rudrata path to close the cycle.