# Incremental Strongly Connected Components with Predictions

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 34 references that are in the map.
- First posted on arXiv 28 Apr 2026.

## Builds on (most cited first, 22 of 22)

- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Faster Matchings via Learned Duals](https://mlsanity.com/paper/2107.09770/) (2021)
- [Learning Augmented Binary Search Trees](https://mlsanity.com/paper/2206.12110/) (2022)
- [Predictive Flows for Faster Ford-Fulkerson](https://mlsanity.com/paper/2303.00837/) (2023)
- [Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions](https://mlsanity.com/paper/2205.09961/) (2022)
- [Sorting with Predictions](https://mlsanity.com/paper/2311.00749/) (2023)
- [Learning-Augmented Maximum Flow](https://mlsanity.com/paper/2207.12911/) (2022)
- [Binary Search with Distributional Predictions](https://mlsanity.com/paper/2411.16030/) (2024)
- [On Dynamic Graph Algorithms with Predictions](https://mlsanity.com/paper/2307.09961/) (2023)
- [On the Complexity of Algorithms with Predictions for Dynamic Graph Problems](https://mlsanity.com/paper/2307.16771/) (2023)
- [Learning-Augmented Priority Queues](https://mlsanity.com/paper/2406.04793/) (2024)
- [Robust Learning-Augmented Dictionaries](https://mlsanity.com/paper/2402.09687/) (2024)
- [Online List Labeling with Predictions](https://mlsanity.com/paper/2305.10536/) (2023)
- [The Predicted-Updates Dynamic Model: Offline, Incremental, and Decremental to Fully Dynamic Transformations](https://mlsanity.com/paper/2307.08890/) (2023)
- [Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow](https://mlsanity.com/paper/2311.18295/) (2023)
- [Incremental Topological Ordering and Cycle Detection with Predictions](https://mlsanity.com/paper/2402.11028/) (2024)
- [Faster Global Minimum Cut with Predictions](https://mlsanity.com/paper/2503.05004/) (2025)
- [Decremental Strongly-Connected Components and Single-Source Reachability in Near-Linear Time](https://mlsanity.com/paper/1901.03615/) (2019)
- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)
- [An efficient strongly connected components algorithm in the fault tolerant model](https://mlsanity.com/paper/1610.04010/) (2016)
- [Stable Matching with Predictions: Robustness and Efficiency under Pruned Preferences](https://mlsanity.com/paper/2602.02254/) (2026)

## Abstract (arXiv)

Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework to design a learned data structure for the incremental strongly connected components (SCC) problem. In this problem, the n vertices of a graph are known a priori and the m directed edges arrive over time. The goal is to efficiently maintain the strongly connected components of the graph after each insert. Our algorithm receives a possibly erroneous prediction of the edge sequence and uses it to precompute partial solutions to support fast inserts. We show that our algorithm achieves nearly optimal bounds with good predictions and its performance smoothly degrades with the prediction error. We also implement our data structure and perform experiments on real datasets. Our empirical results show that the theory is predictive of practical runtime improvements.