Single pair shortest path algorithm with time a constraint

Question

I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional constraint "the total time should not exceed T time units", then the problem becomes much harder.

More formally:

The input consists of a set of n cities and m roads between pairs of cities. There can be multiple roads between a pair of cities $(i, j)$. For each road, you are given its departure city $x_i$, its destination city $y_i$, its duration $d$, and its cost $c$. The objective is to find the cheapest path between a pair of cities $(a, b)$ such that the cost is minimized while keeping the duration less than the maximum duration $T$.

I tried thinking on the lines of Dijkstra's and modifying the graph so that it is in some way possible to run a shortest path algorithm on it, but there seems to be no trivial way of doing this. Simple solutions like (follow a greedy strategy until you exceed the time limit, and then move on to the next element in the priority queue) don't seem to work because the use of a priority queue in the Dijkstra's algorithm and DEQUEUING the minimum element from the priority queue behave like destructive operations. There is a need to backtrack (of sorts) but the shortest path algorithms visit each node in the graph only once.

I've tried thinking about other simpler approaches using the Bellman-Ford algorithm, but the time complexity of the algorithm I turned out writing depended on $T$ (which is not very desirable).

I spent almost 2 days on this and every solution I try either seems to not work, or runs in exponential time. Is this problem NP hard or are there polynomial time solutions possible?

P.S. I am not looking for a practical implementation of this problem, just an algorithm that can solve this problem in polynomial time. Although any thoughts about how to efficiently implement this would be more than welcome :)

Answer 1

Your problem is NP-hard: The partition problem reduces to it as follows:

Let $ S = \{s_0, ... , s_{n-1} \} $ be a multiset of non-negative integers.

Construct cities $ \{ c_0, ... , c_n \} $, with each city $ c_i $ having 2 roads to $ c_{i+1} $, one with duration $ 0 $ and cost $ s_i $, the other with duration $ s_i $ and cost $ 0 $.

Then find the minimum-distance path from $ c_0 $ to $ c_n $ with total duration at most $ \frac 1 2 \sum S $. This path has equal cost and duration iff $ S $ can be partitioned into subsets of equal sum.