I see the disagreement: I was constructing a one-way fare by putting together known (published) fares. That's the easy problem.
If the airline can make arbitrary rules, and you are putting together a round-trip fare, then it's easy to be NP-hard (or even harder, if the rules can be that hard to check; e.g. refer to other rules).