Incremental Strongly Connected Components with Predictions
Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, Nathan Vosburg · 2026
Read Incremental Strongly Connected Components with Predictions by Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, Nathan Vosburg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26062.txt.
Introduction
Deng and seven colleagues design a learned data structure for a graph problem: tracking its strongly connected parts as directed edges arrive one by one, with all vertices known in advance. Their method takes a possibly faulty guess of the edge order and precomputes partial answers to speed up each insertion. With good guesses it hits nearly optimal bounds, and its speed falls gradually as guess error grows. Tests on real data sets confirm that the theory gains show up in practice.
Catalog record
| CREATOR | Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, Nathan Vosburg |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54804 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26062
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Incremental Strongly Connected Components with Predictions Ronald Deng, Samuel McCauley, Aidin Niaparast, Helia Niaparast, Bennett Ptak, Shirel Quintanilla, Shikha Singh, Nathan Vosburg Abstract 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 n vertices of a graph are known a priori and the m 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. 1 Introduction Incremental computation on graphs is a fundamental primitive in many database and optimization problems. In an incremental graph problem, the vertices of the graph G are known ahead of time and the edges are revealed over time. The goal is to design an efficient data structure for answering queries at time t about some property (such as connectivity or shortest path) of the current graph G_{t} . Designing fast worst-case algorithms for incremental graph problems is an area of extensive research [ 7 , 3 , 5 , 12 , 13 ] . Algorithms designed to be fast in the worst case provide strong guarantees against adversarial inputs. However, these algorithms fail to exploit the correlations in the structure of typical instances. As most computations are performed repeatedly on similar datasets, heuristics optimized for domain specific inputs tend to be faster in practice. A growing body of work, known as algorithms with predictions [ 25 ] , seeks to bridge the gap between simple heuristics that lack strong theoretical guarantees and more complex worst-case algorithms that are provably efficient but often impractical. The main idea is to use machine-learned predictions to capture correlations in the input instances and leverage them to guide algorithmic decisions. Predictions are particularly effective for online or dynamic problems, where the input is not known ahead of time. Predictions trained on historical data can then serve as a proxy for future inputs—turning a hard online problem into an easier-to-solve offline one. Using such predictions, an algorithm can then precompute partial solutions ahead of time and consequently perform faster updates and queries at runtime. The algorithms designed in this framework are referred to as learning-augmented or learned algorithms. The running time of a learned algorithm is measured in terms of the quality of the prediction—the bound is stated in terms of both the size of the input and the prediction error. Ideally, a learned algorithm for an online problem (1) is nearly as fast as the best-offline solution when the prediction is perfect, (2) has bounded worst-case performance cost when the prediction is arbitrarily wrong, and (3) has performance that degrades gracefully with error. These properties in order are referred to as consistency, robustness , and smoothness respectively in the literature. Thus, learned algorithms leverage good predictions to be fast and have provable safeguards against bad predictions. Incremental SCC. In this paper, we study the incremental strongly connected components (SCC) problem in the algorithms with predictions model. In this problem, the n vertices V of a directed graph G are known a priori and the m directed edges E are inserted one by one. Let e_{1},\dots,e_{m} denote the sequence of edges and let G_{t}=(V,\{e_{1},\ldots,e_{t}\}) denote the graph at time t . The goal is to maintain the strongly connected components of G_{t} at all times t . A strongly connected component S\subseteq V is a maximal set of vertices of G such that every pair of vertices u,v are mutually reachable , that is, there is a directed path from v to u and vice versa. Maintaining SCCs is a fundamental building block in many applications, e.g. social networks [ 9 ] , graph processing [ 34 ] , program analysis [ 14 ] and fault-tolerant networks [ 2 ] . DFS-based approaches such as Tarjan’s algorithm [ 31 ] can compute the SCCs of a static offline graph G in O(n+m) time. As a step towards solving the incremental SCC problem, consider the offline incremental problem . In this variant, the edge insert sequence \sigma=e_{1},e_{2},\ldots,e_{m} is known ahead of time and the goal is to design a data structure to answer queries about the SCCs of each intermediate graph G_{t} . Naively running Tarjan’s repeatedly takes O(m^{2}) time. 1 1 1 We assume m\geq n to simplify the runtimes. A folklore divide-and-conquer approach [ 28 ] improves upon this naive approach and solves the offline incremental SCC problem in O(m\log m) total time. Offline to Learned Incremental SCC. To design a learned algorithm for the online incremental problem , we assume that a prediction \hat{\sigma} of the edge sequence \sigma is given to the algorithm. We define the prediction error \eta as the maximum error between when an edge was predicted to arrive in \hat{\sigma} and its actual arrival time in \sigma . To ensure this metric is well-defined, we assume that \hat{\sigma} is a permutation of \sigma (we discuss this assumption further in Section 2.1 ). If the prediction is perfect ( \eta=0 ), the problem reduces to the offline incremental variant. If the prediction is arbitrarily erroneous ( \eta=m ), the algorithm effectively gets no information about the input and the problem reduces to the worst-case model. The main challenge is to design an algorithm that smoothly interpolates between the two regimes as a function of the prediction error \eta . 1.1 Our Contributions One of our main contributions is designing the first learned data structure for the incremental SCC problem which is consistent, robust and smooth with respect to the prediction error. Theorem 1.1 . We design a learned data structure that, given prediction \hat{\sigma} with error \eta , maintains the strongly connected components of the graph in total time O(m\log m\cdot\max\{\eta,1\}) for m inserts. Queries about the SCC of a given vertex take O(1) time. To put this result in context, notice that if the edge arrivals are reasonably predictable (e.g. \eta=O(\text{polylog}(m))) , our algorithm for the online incremental problem is nearly as fast as the offline variant. The algorithmic idea is to use a divide-and-conquer approach on the predicted edge sequence \hat{\sigma} to recursively precompute solutions to partial subproblems using Tarjan’s algorithm. As edges arrive that are different from \hat{\sigma} , our algorithm updates the prediction and lazily recomputes the affected subproblems. At a high level, we show that we can bound the number of times each subproblem is recomputed by the prediction error \eta and thus lose an \eta factor over the offline incremental algorithm. Robustness to Error. The running time of our algorithm grows with \eta —in fact, for sufficiently high \eta , our algorithm may be slower than known worst-case techniques. However, the algorithm can be made