Abstract

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.

Software

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.

Instances

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.

Kronecker/csize

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

Kronecker/growing

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

Real-World Instances

KONECT

Fully dynamic instances from the Koblenz Network Collection:

• Wikipedia, fr (dynamic)
• Wikipedia, de (dynamic)
• Wikipedia, it (dynamic)
• Wikipedia, nl (dynamic)
• Wikipedia, pl (dynamic)
• Wikipedia, simple en (dynamic)

KONECT shuffled

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

SNAP/as-caida

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.

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:

@inproceedings{hhs-dssr-2020,
  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},
}