Twice the optimal result is terrible, though.

Luckily, there are pretty good heuristic solutions that work well in practice.

That's worst case. It means the most adversarial graph imaginable gets a time twice as long as the shortest possible.