Originally Posted by
sethb
There are some published fares, including direct flights and connections. Those are all input to the program. It is then an easy algorithm to find all least-cost routings between cities.
I'll admit it...I was wrong. ...The problem is actually NP-hard, not NP-complete. But everything else I said is still true. If you have an algorithm to solve an NP-hard problem in polynomial time, you have proven that P=NP and that wins you the $1 million. (An NP-complete problem can be verified in polynomial time, but that's not the case here.)
The problem with your logic is that you're still assuming that the price of the ticket only increases as fare components are added. This is not true. You cannot reliably price a ticket until the entire ticket is known, or even make claims such as "the ticket will be at least $X." For example, adding a fare component can change which location is considered the destination vs. the stop over. Adding a fare component can change whether or not the ticket qualifies as round/circle trip. Adding a fare component can exceed a minimum stay requirement or fulfill a Saturday stay requirement.
See this article:
http://www.msri.org/people/members/s...s/airfares.pdf
Obviously, if you bound the problem by saying "I only want to see non-stop fares" or "I won't leave the US to connect on an otherwise domestic itinerary" or "my itinerary must be complete within X days" then you can solve the problem in a reasonable period of time. But, that doesn't mean its not still NP-hard. It just means you've reduced the problem to a degree where all of the possibilities can be checked.