[lastofthemojito]

Here's a excellent presentation by a co-founder of ITA Software to an MIT compsci course, entitled Computational Complexity of Air Travel Planning

http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf