Even in hard cases it's not usually too hard
Somtimes the graph is disconnected
There aren't usually very many nodes
Branch-and-bound techniques work just fine
