10.3.1 Traveling Salesman Problem

A Hamiltonian cycle in an undirected graph is a simple cycle that passes through every vertex exactly once.

Optimization Problem: Given a complete, weighted graph, find a minimum-weight Hamiltonian Cycle.

Decision Problem: Given a complete, weighted graph and an integer k, does there exist a Hamiltonian cycle with total weight at most k.