Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subject to edge deletions and insertions. It is one of the most fundamental problems on graphs and appears directly or indirectly in many and varied applications. While there has been theoretical work on this problem, showing both linear conditional lower bounds for the fully dynamic problem and insertions-only and deletions-only upper bounds beating these conditional lower bounds, there has been no experimental study that compares the performance of fully dynamic reachability algorithms in practice. Previous experimental studies in this area concentrated only on the more general all-pairs reachability or transitive closure problem and did not use real-world dynamic graphs.

In this paper, we bridge this gap by empirically studying an extensive set of algorithms for the single-source reachability problem in the fully dynamic setting. In particular, we design several fully dynamic variants of well-known approaches to obtain and maintain reachability information with respect to a distinguished source. Moreover, we extend the existing insertions-only or deletions-only upper bounds into fully dynamic algorithms. Even though the worst-case time per operation of all the fully dynamic algorithms we evaluate is at least linear in the number of edges in the graph (as is to be expected given the conditional lower bounds) we show in our extensive experimental evaluation that their performance differs greatly, both on generated as well as on real-world instances.


We implemented all algorithms as part of the open-source modular algorithms library Algora. Our experiments were run using the following versions (including link to sources): Algora|Core v1.1, Algora|Dyn v1.0.


We used three sets of instances of fully dynamic directed graphs:

Random Instances

All instances were generated according to the Erdős-Rényi model G(n, m).

Kronecker Instances

We generated instances from sequences of stochastic Kronecker graphs (‘‘snapshots’’) using the differences in two subsequent snapshots as updates. The Kronecker graphs were generated using the krongen tool, which is part of SNAP, with the initiator matrices given in Kronecker Graphs: An Approach to Modeling Networks by Leskovec e.a.


Each instance was generated from 10 snapshot graphs, each of which was obtained in 17 rounds.

Instance Vertices used as single source Download
answers 0,2,8,16,64,256,2048,8192,32768,65536 answers.xz
as-newman 0,2,4,16,32,128,256,512,8192,16384 as-newman.xz
as-routeviews 0,2,8,32,128,256,512,4096,8192,65536 as-routeviews.xz
atp-gr-qc 0,4,12,34,512,24576,32768,33920,34304,66560 atp-gr-qc.xz
bio-proteins 0,1,4,32,128,256,1024,2048,4096,32768 bio-proteins.xz
blog-nat05-6m 0,1,4,64,128,256,512,16384,32768,65536 blog-nat05-6m.xz
blog-nat06all 0,1,2,8,16,64,512,4096,8192,65536 blog-nat06all.xz
ca-dblp 0,2,4,24,65,2048,9216,16384,32768,65536 ca-dblp.xz
ca-gr-qc 0,2,8,16,72,4096,16384,32786,65536,65537 ca-gr-qc.xz
ca-hep-ph 0,2,4,8,16,64,256,512,2048,65536 ca-hep-ph.xz
ca-hep-th 0,1,8,32,40,65,128,256,512,1024 ca-hep-th.xz
cit-hep-ph 0,2,4,8,64,2048,8192,16384,32768,65536 cit-hep-ph.xz
cit-hep-th 0,1,32,256,1024,2048,4096,8192,16384,65536 cit-hep-th.xz
delicious 0,1,4,8,128,256,512,8192,32768,65536 delicious.xz
email-inside 0,1,4,16,64,1024,4096,8192,16384,32768 email-inside.xz
epinions 0,1,4,8,64,512,2048,4096,16384,32768 epinions.xz
flickr 0,2,32,64,128,1024,2048,8192,32768,65536 flickr.xz
gnutella-25 0,1,2,18,20,32,64,128,2048,5120 gnutella-25.xz
gnutella-30 0,2,64,128,520,8200,16384,32768,40960,65536 gnutella-30.xz
web-notredame 0,1,4,64,256,512,4096,8192,32768,65536 web-notredame.xz


Each instance was generated from 15 snapshot graphs, where the first was obtained in 5 rounds, the second in 6, and so on.

Instance Vertices used as single source Download
answers 0,2,8,9,10,12,16,17,19,29 answers.xz
as-newman 0,1,2,4,6,7,8,9,16,20 as-newman.xz
as-routeviews 0,1,2,5,8,10,12,16,20,24 as-routeviews.xz
atp-gr-qc 5,8,9,10,17,18,21,23,24,31 atp-gr-qc.xz
bio-proteins 0,1,2,4,5,6,7,8,12,16 bio-proteins.xz
blog-nat05-6m 0,1,2,5,10,12,16,17,19,20 blog-nat05-6m.xz
blog-nat06all 0,2,3,4,7,8,9,16,17,18 blog-nat06all.xz
ca-dblp 0,2,4,5,8,9,10,16,17,24 ca-dblp.xz
ca-gr-qc 0,3,4,5,6,8,14,26,28,30 ca-gr-qc.xz
ca-hep-ph 0,1,2,3,4,5,9,16,26,31 ca-hep-ph.xz
ca-hep-th 0,1,3,4,7,8,12,17,19,30 ca-hep-th.xz
cit-hep-ph 0,1,2,4,5,6,8,16,26,30 cit-hep-ph.xz
cit-hep-th 0,1,3,8,9,12,17,20,24,28 cit-hep-th.xz
delicious 0,2,4,5,8,9,10,17,18,20 delicious.xz
email-inside 0,1,2,4,5,8,16,18,20,24 email-inside.xz
epinions 0,1,2,4,5,6,8,10,15,24 epinions.xz
flickr 0,1,2,3,4,12,16,17,20,24 flickr.xz
gnutella-25 0,2,3,8,11,16,17,19,20,28 gnutella-25.xz
gnutella-30 2,3,4,8,13,16,20,21,28,31 gnutella-30.xz
web-notredame 0,2,4,5,6,8,16,17,19,20 web-notredame.xz

Real-World Instances


Fully dynamic instances from the Koblenz Network Collection:

KONECT shuffled

Instances obtained from the KONECT instances by randomly assigning a new timestamp to each update.

Original Instance Shuffled Instances  
Wikipedia, fr (dynamic) fr_shuffled_00.xzfr_shuffled_01.xzfr_shuffled_02.xzfr_shuffled_03.xzfr_shuffled_04.xz  
Wikipedia, de (dynamic) de_shuffled_00.xzde_shuffled_01.xzde_shuffled_02.xzde_shuffled_03.xzde_shuffled_04.xz  
Wikipedia, it (dynamic) it_shuffled_00.xzit_shuffled_01.xzit_shuffled_02.xzit_shuffled_03.xzit_shuffled_04.xz  
Wikipedia, nl (dynamic) nl_shuffled_00.xznl_shuffled_01.xznl_shuffled_02.xznl_shuffled_03.xznl_shuffled_04.xz  
Wikipedia, pl (dynamic) pl_shuffled_00.xzpl_shuffled_01.xzpl_shuffled_02.xzpl_shuffled_03.xzpl_shuffled_04.xz  
Wikipedia, simple en (dynamic) simple_shuffled_00.xzsimple_shuffled_01.xzsimple_shuffled_02.xzsimple_shuffled_03.xzsimple_shuffled_04.xz  


A fully dynamic instance obtained from the 122 snapshot graphs that belong to the as-caida instance from the Stanford Large Network Dataset Collection by using again the differences in two subsequent snapshot graphs as updates.

Instance Vertices used as single source Download
as-caida 209,701,702,1239,2914,3356,3549,3561,6461,7018 as-caida.xz

License and Bibliography

Our implementation of the algorithms is available as part of Algora under the GNU Public License (GPL) version 3.

If you publish results using our algorithms, instances, or implementation, please acknowledge our work by citing our paper as follows:

  author    = {Hanauer, Kathrin and Henzinger, Monika and Schulz, Christian},
  editor    = {Blelloch, Guy E. and Finocchi, Irene},
  title     = {Fully Dynamic Single-Source Reachability in Practice: An Experimental Study},
  booktitle = {Proceedings of the Symposium on Algorithm Engineering and Experiments,
               {ALENEX} 2020, Salt Lake City, UT, USA, January 5-6, 2020},
  pages     = {106--119},
  publisher = {{SIAM}},
  year      = {2020},
  url       = {https://doi.org/10.1137/1.9781611976007.9},
  doi       = {10.1137/1.9781611976007.9},