Hacker News Reader

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.