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(mn) time 1 [GRKL01, LR01] given more than twenty years ago have remained the stateof-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 2 , our algorithms run in time O(n 2 ) and, O(mn 3/5 ) or better, respectively. More specifically, the algorithm for sparse digraphs runs in time O(mn (3-α)/5 ) for graphs with n 1+α edges for any real α ∈ [0, 1/2].

• Rutgers.