# Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow

arXiv: https://arxiv.org/abs/2311.18295 · HTML: https://mlsanity.com/paper/2311.18295/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Nov 2023.

## Built on by (most cited first, 4 of 4)

- [Generalized Attention Flow: Feature Attribution for Transformer Models via Maximum Flow](https://mlsanity.com/paper/2502.15765/) (2025)
- [Swim till You Sink: Computing the Limit of a Game](https://mlsanity.com/paper/2408.11146/) (2024)
- [Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation](https://mlsanity.com/paper/2505.03955/) (2025)
- [Incremental Strongly Connected Components with Predictions](https://mlsanity.com/paper/2604.26062/) (2026)

## Abstract (arXiv)

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, s-t shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a mo(1)-approximate minimum-ratio cycle in fully dynamic graphs in amortized mo(1) time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold F. By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above. At a high level, our algorithm dynamizes the ℓ1 oblivious routing of Rozhovn-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to extract an approximate minimum ratio cycle from the structure of the oblivious routing. To maintain the oblivious routing, we use tools from concurrent work of Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for shortest paths, in order to maintain a sparse neighborhood cover in fully dynamic graphs. To find a cycle, we first show that an approximate minimum ratio cycle can be represented as a fundamental cycle on a small set of trees resulting from the oblivious routing. Then, we find a cycle whose quality is comparable to the best tree cycle. This final cycle query step involves vertex and edge sparsification procedures reminiscent of previous works, but crucially requires a more powerful dynamic spanner which can handle far more edge insertions. We build such a spanner via a construction that hearkens back to the classic greedy spanner algorithm.