A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. Ashvinkumar, Bernstein, and Karczmarz (SODA 2025) gave the first randomized bicriteria $(1+\epsilon ,1+\epsilon )$-approximate algorithm on directed graphs running in sub-$mn$ time, answering a problem posed by Bernstein (SODA 2012). We substantially improve this on two fronts, supplying a deterministic bicriteria $(1+\epsilon ,1+\epsilon )$-approximate algorithm running in near-linear time. Our approach straightforwardly generalizes to more than two resources. For $k$ resources, a deterministic $(1+{\epsilon }_1,\dots ,1+{\epsilon }_k)$-approximate algorithm running in near-linear time is possible, with ${\epsilon }_1=\dots ={\epsilon }_k=\epsilon$.