Fully dynamic strong connectivity and reachability in digraphs
TL;DR
A deterministic fully dynamic algorithm that simultaneously maintains SCCs and reachability in directed graphs and significantly outperforms repeated offline recomputation in practical scenarios is presented.
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 + n 2 ) 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 con-trol flow graphs (CFGs). Experimental evaluation on random graphs and real program CFGs shows that the algorithm significantly outperforms repeated offline recomputation in practical scenarios.