### NAME:

### PRECEPT:

### LOGIN:

###
COS 226 Exercises on Reductions

**1. **
Give a polynomial reduction from HAM-PATH to
SHORTEST-SIMPLE-PATH.
HAM-PATH: given an digraph, is there
a path that visits each vertex exactly once.

SHORTEST-SIMPLE-PATH: given a directed graph
with edge weights (positive or negative) and
two distinguished vertices s and t, find the
shortest simple path from s to t.
(A simple path is a path that visits each
vertex at most once.)

Remark: HAM-PATH is a notoriously difficult problem
(NP-complete) for which no poly-time algorithms are
known (or likely to exist). This reduction implies
that the general version of the shortest path
problem (allowing negative edge weights and negative
cycles) is intractable.