I was surprised that Gruhn didn't include this in his list of problems where the NP-hardness is not that important in practice.

I think the Ford-Fulkerson maximum flow algorithm may be another example.