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.