Originally Posted by
sethb
False. It's actually the "shortest-path problem" which is quite well known and easily solvable. It is nowhere near NP-complete.
And in the real world, it's even easier; once I've found a way to get from AAA to BBB for $222, any route that's already over $222 doesn't need to be extended, because it already lost.
How long of a layover do you allow for? Remember, with broken fares the normal 4 hour domestic requirement does not apply. I've seen Orbitz price broken fares with overnight layovers to save a few bucks. Most other sites typically seem to limit layovers on broken fares to the nominal 4 hours used for through fares. How about connections between co-terminals? Orbitz prices broken fares where you arrive at ORD and then depart from MDW. Is that a reasonable search requirement? Then there's the issue of getting bucket inventory levels for all the possible flight options from the GDS'es. I don't believe that's a particularly quick operation. In short, I don't think it's quite as trivial as a search issue as you seem to believe. Also, as noted above, the connection options can get particularly obscure and long if you don't bound for connection time.