# Proving following problem NP Hard using known NP Hard partition problem

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? ## migrated from cstheory.stackexchange.comOct 21 '12 at 18:32 This question came from our site for theoretical computer scientists and researchers in related fields. ## 1 Answer 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.