Abstract

The fully dynamic transitive closure problem asks to maintain reachability information in a directed graph between arbitrary pairs of vertices, while the graph undergoes a sequence of edge insertions and deletions. The problem has been thoroughly investigated in theory and many specialized algorithms for solving it have been proposed in the last decades. In two large studies [Frigioni ea, 2001; Krommidas and Zaroliagis, 2008], a number of these algorithms have been evaluated experimentally against simple, static algorithms for graph traversal, showing the competitiveness and even superiority of the simple algorithms in practice, except for very dense random graphs or very high ratios of queries. A major drawback of those studies is that only small and mostly randomly generated graphs are considered.

In this paper, we engineer new algorithms to maintain all-pairs reachability information which are simple and space-efficient. Moreover, we perform an extensive experimental evaluation on both generated and real-world instances that are several orders of magnitude larger than those in the previous studies. Our results indicate that our new algorithms outperform all state-of-the-art algorithms on all types of input considerably in practice.

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.2, Algora|Dyn v1.1.

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.

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-dtc-2020,
  author    = {Hanauer, Kathrin and Henzinger, Monika and Schulz, Christian},
  editor    = {Faro, Simone and Cantone, Domenico},
  title     = {Faster Fully Dynamic Transitive Closure in Practice},
  booktitle = {18th International Symposium on Experimental Algorithms, {SEA} 2020,
               June 16-18, 2020, Catania, Italy},
  series    = {LIPIcs},
  volume    = {160},
  pages     = {14:1--14:14},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2020},
  url       = {https://doi.org/10.4230/LIPIcs.SEA.2020.14},
  doi       = {10.4230/LIPIcs.SEA.2020.14},
}