# Incremental Shortest Paths in Almost Linear Time via a Modified Interior Point Method

Article · Yang P. Liu

- Archive id: arxiv:2506.19207
- Published: 2025-06-24
- Venue: ACM Symposium on Theory of Computing (STOC)
- DOI: https://doi.org/10.1145/3798129.3800733
- arXiv: https://arxiv.org/abs/2506.19207
- Citations: 0
- Source URL: https://arxiv.org/abs/2506.19207
- PDF: https://arxiv.org/pdf/2506.19207
- Provenance: arxiv

## Abstract

We give an algorithm that takes a directed graph $G$ undergoing $m$ edge insertions with lengths in $\[1, W\]$, and maintains $(1+ε)$-approximate shortest path distances from a fixed source $s$ to all other vertices. The algorithm is deterministic and runs in total time $m^{1+o(1)}\\log W$, for any $ε\> \\exp(-(\\log m)^{0.99})$. This is achieved by designing a nonstandard interior point method to crudely detect when the distances from $s$ other vertices $v$ have decreased by a $(1+ε)$ factor, and implementing it using the deterministic min-ratio cycle data structure of \[Chen-Kyng-Liu-Meierhans-Probst, STOC 2024\].

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

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
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.