Fully dynamic strong connectivity and reachability in digraphs

Morse, Gregory and Kozsik, Tamás (2026) Fully dynamic strong connectivity and reachability in digraphs. ANNALES MATHEMATICAE ET INFORMATICAE, 63. pp. 88-106. ISSN 1787-6117

Preview

Text 88_106.pdf - Published Version Download (740kB) | Preview

Abstract

Computing strongly connected components (SCCs) and reachability in directed graphs is fundamental in compilers, static analysis, and many graph algorithms. While efficient offline algorithms are well known, maintaining this information dynamically under both edge insertions and deletions remains challenging. This paper presents a deterministic fully dynamic algorithm that simultaneously maintains SCCs and reachability in directed graphs. The approach combines a union–find structure for efficient merging of SCCs during edge insertions with localized recomputation of SCCs using Nuutila’s algorithm when deletions potentially split a component. Reachability information is maintained at the SCC level and propagated through the condensation DAG. For a current graph with n vertices and m edges, the resulting algorithm supports O(1) reachability queries while updates have worst-case complexity O(m+n2) due to reachability propagation. Although this does not improve the best known theoretical bounds for specialized dynamic algorithms, the method is simple, deterministic, and well suited to sparse graphs such as control flow graphs (CFGs). Experimental evaluation on random graphs and real program CFGs shows that the algorithm significantly outperforms repeated offline recomputation in practical scenarios.

Actions (login required)

Edit Item