**Next:**10.3.2
Subset Sum**Up:**10.3
Examples of some Intractable Problems**Previous:**10.3
Examples of some Intractable Problems

##
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.*

eEL,CSA_Dept,IISc,Bangalore