# Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs

Preprint · Vikrant Ashvinkumar, Aaron Bernstein, Adam Karczmarz

- Archive id: arxiv:2410.17179
- Published: 2024-10-22
- arXiv: https://arxiv.org/abs/2410.17179
- Source URL: https://arxiv.org/abs/2410.17179
- PDF: https://arxiv.org/pdf/2410.17179
- Provenance: arxiv

## Abstract

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 \[Garey and Johnson, 1979\] $(1+\\varepsilon)$-approximate algorithms running in $\\tilde{O}(mn)$ time \[Goel et al., INFOCOM'01; Lorenz and Raz, Oper. Res. Lett.'01\] given more than twenty years ago have remained the state-of-the-art for directed graphs. An open problem posed by \[Bernstein, SODA'12\] -- who gave a randomized $m\\cdot n^{o(1)}$ time bicriteria $(1+\\varepsilon, 1+\\varepsilon)$-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+\\varepsilon, 1+\\varepsilon)$-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 $\\tilde{O}(n^2)$ and $\\tilde{O}(mn^{3/5})$ or better, respectively. More specifically, the algorithm for sparse digraphs runs in time $\\tilde{O}(mn^{(3 - α)/5})$ for graphs with $n^{1 + α}$ edges for any real $α\\in \[0,1/2\]$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.