2026-09-05T07:04:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26053 2026-06-23T13:18:40Z ddc:004 open_access

Incremental Strongly Connected Components with Predictions Deng, Ronald McCauley, Samuel Niaparast, Aidin Niaparast, Helia Ptak, Bennett Quintanilla, Shirel Singh, Shikha Vosburg, Nathan algorithms with predictions learning augmented algorithms incremental graph algorithms strongly connected components data structures 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ronald Deng and Samuel McCauley and Aidin Niaparast and Helia Niaparast and Bennett Ptak and Shirel Quintanilla and Shikha Singh and Nathan Vosburg 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.17 urn:nbn:de:0030-drops-260530 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.17 eng https://creativecommons.org/licenses/by/4.0/legalcode