Reduction: RUDRATA CYCLE → TSP(Travel Salesman)

Given a graph $G = (V,E)$, construct the following instance of the TSP:

• The set of cities is the same as $V$

• The distance between cities $u$ and $v$ is 1 if $\{u,v\}$ is an edge of $G$ and $1+\alpha$ otherwise, for some $\alpha > 1$ to be determined.

• The budget $g$ of TSP $= |V|$

Easy to see that if $G$ has a Rudrata cycle, then the same cycle is also a tour within the budget of the TSP instance

Conversely, if $G$ has no Rudrata cycle, then there is no solution: cheapest possible TSP tour has cost at least $n + \alpha$ (must use at least one edge of length $1+\alpha$, and total length of all $n-1$ others is at least $n-1$).

We introduced the parameter $\alpha$ because by varying it we can obtain interesting results

• $\alpha = 1$
  • all distances are either 1 or 2, and instance of TSP satisfies the triangle inequality.
  • This is a special case of TSP which is of practical importance, because it can be efficiently approximated.

• $\alpha$ is large
  • resulting instance of the TSP may not satisfy the triangle inequality
  • But either it has a solution of cost $n$ or less, or all solutions have cost at least $n + \alpha$ (which now can be arbitrarily larger than $n$), nothing in-between!
  • This is called an important gap property such that unless $P = NP$, no approximation algorithm is possible for this particular instance