Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs

In the restricted shortest paths problem, we are given a graph G whose edges are assigned two non-negative weights: lengths and delays, a source s, and a delay threshold D. The goal is to find, for each target t, the length of the shortest (s, t)-path whose total delay is at most D. While this problem is known to be NP-hard [GJ79], (1 + ε)-approximate algorithms running in O^e(mn) time¹ [GRKL01, LR01] given more than twenty years ago have remained the state-of-the-art for directed graphs. An open problem posed by [Ber12] — who gave a randomized m · n^o(1) time bicriteria (1 + ε, 1 + ε)-approximation algorithm for undirected graphs — asks if there is similarly an o(mn) time approximation scheme for directed graphs. We show two randomized bicriteria (1 + ε, 1 + ε)-approximation algorithms that give an affirmative answer to the problem: one suited to dense graphs, and the other that works better for sparse graphs. On directed graphs with a quasi-polynomial weights aspect ratio², our algorithms run in time O^e(n²) and, O^e(mn³/⁵) or better, respectively. More specifically, the algorithm for sparse digraphs runs in time O^e(mn⁽³−α)/⁵) for graphs with n^1+α edges for any real α ∈ [0, 1/2].