Travelling salesman problem with small edge weights
Travelling salesman remains NP-complete even if you restrict to two different edge weights $a&lt;b$.  Reduce from Hamiltonian cycle by giving weight&nbsp;$a$ to every edge and weight&nbsp;$b$ to every non-edge.  Then the resulting complete graph has a TSP tour of length&nbsp;$na$ (where $n$&nbsp;is the number of vertices) if, and only if, the original graph has a Hamiltonian cycle.