There's a paper somewhere (I think from one of the ITA founders) about how flight search is actually NP-complete. I haven't looked carefully but I think these

There's a paper somewhere (I think from one of the ITA founders) about how flight search is actually NP-complete. I haven't looked carefully but I think these slides cover a lot of it. http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf http://www.ai.mit.edu/courses/6.034f/psets/ps1/airtravel.pdf "One interesting result not written up here is that even completely fixing the flights and fares of a ticket, so that the only remaining question is how to partition the fares into priceable units, is NP-complete. This is interesting because only flight and fare information makes its way onto printed tickets, not the grouping of fares into PUs. Therefore the problem of just validating a printed ticket is worst-case NP-complete, though it is rarely difficult in practice."