Proving following problem NP Hard using known NP Hard partition problem

Question

Least cost travel by intermixing different airline routes having linear discount functions:

Lowest air fare route chosen by mixing different routes provided by different airline having different discount functions (like some airline can give 25% discount if fare crosses $5k) so that total cost of travel is minimized after intermixing of different airline routes

This is a graph problem. Let $E(k)$ be the set of edges/routes flown by $k$-th airline, also given cost of travel associated with each edge.

For $n$ airlines we have $n$ sets of edges i.e $E(k)=\{\mbox{some edges}\}$ for all $k=1.. n$. We need to find the route from given source $s$ to given destination $t$ such that we end up paying least fare among all possible routes. There is no restriction on number of edges in a route.

This is an NP-hard problem. How can I prove it?

Answer 1

Assuming that an "airport" cannot be visited more than once, you can reduce HAMILTONIAN PATH to your problem: given a graph $G = (V,E)$, $|V|=n$; suppose that there are two airlines such that $E(1)=E(2)=E$ (i.e. both airlines cover all edges). Then set the price of each edge = $1$. One of the two companies gives no discount, the other gives a (big) discount $d$% (such that $n - \frac{n * d}{100} < 1$) if the cost of the travel is $\geq n$.

Then $G$ has an Hamiltonian path from $s$ to $t$ if and only if the minimum cost of the travel is $< 1$ (i.e. the airline which gives the discount is more convenient).

Note: if an airport can be visited more than once I think that the problem is no more NP-hard (but I didn't think of it too much). In this case a modified version of a shortest path algorithm should work: just augment the shortest path traversing multiple times an edge of each airline and check if the total cost decreases after reaching the discount treshold.