An experimental comparison of tree-data structures for connectivity queries on fully-dynamic undirected graphs (Extended Version)

Qing Chen, Michael H. Böhlen, Sven Helmer · 2025

Read An experimental comparison of tree-data structures for connectivity queries on fully-dynamic undirected graphs (Extended Version) by Qing Chen, Michael H. Böhlen, Sven Helmer (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-02278.txt.

Introduction

Chen, Böhlen, and Helmer present a study from twenty twenty-five comparing tree data structures for connectivity queries on changing graphs. Graphs with frequent edge insertions and deletions need fast connectivity answers. Many structures have been proposed over decades for that task. Few were ever implemented, let alone tested head-to-head. The team build reference implementations for the main proposals. They benchmark them across a wide range of graph types. No current solution is ready for direct deployment, they find.

Each structure shows critical practical weaknesses in their tests. Balanced structures carry heavy space and time overhead. Lean structures degrade badly in worst cases. Maintenance costs burden the balanced options further. The authors close with guidance for building robust versions.

Catalog record

CREATORQing Chen, Michael H. Böhlen, Sven Helmer
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-02278

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An experimental comparison of tree-data structures for connectivity queries on fully-dynamic undirected graphs (Extended Version) Qing Chen, Michael H. Böhlen, Sven Helmer Abstract . During the past decades significant efforts have been made to propose data structures for answering connectivity queries on fully dynamic graphs, i.e., graphs with frequent insertions and deletions of edges. However, a comprehensive understanding of how these data structures perform in practice is missing, since not all of them have been implemented, let alone evaluated experimentally. We provide reference implementations for the proposed data structures and experimentally evaluate them on a wide range of graphs. Our findings show that the current solutions are not ready to be deployed in systems as is, as every data structure has critical weaknesses when used in practice. Key limitations that must be overcome are the space and time overhead incurred by balanced data structures, the degeneration of the runtime of space-efficient data structures in worst case scenarios, and the maintenance costs for balanced data structures. We detail our findings in the experimental evaluation and provide recommendations for implementing robust solutions for answering connectivity queries on dynamic graphs. The source code, data, and/or other artifacts have been made available at https://github.com/qingchen3/Imp_bench_dyn . 1. Introduction It is common lore that asymptotically faster algorithms are preferable over asymptotically slower alternatives. Since many years this understanding has served our community as a coarse guideline for designing and selecting data structures and algorithms. In recent years, however, a number of solutions have been proposed where more fine-grained evaluations are needed to gain actionable insights into the properties of data structures and algorithms ( Roughgarden 2019 ; Augsten et al. 2010 ; Hu and Yi 2019 ; Ding et al. 2021 ; Fuchs et al. 2022 ) . A problem where insights beyond worst case asymptotic complexity and amortized costs are missing is the connectivity problem for fully dynamic graphs. Connectivity queries over fully dynamic graphs consider graphs with possibly frequent edge insertions and deletions and determine if two vertices are connected. While this fundamental problem has been studied extensively on a theoretical level for dynamic graphs ( Fan and Tian 2022 ; Puatracscu and Demaine 2004 ; Eppstein et al. 1993 ; Henzinger and Fredman 1998 ; Patrascu and Thorup 2007 ; Eppstein et al. 1992 ) and various data structures ( Henzinger and King 1995 ; Wulff-Nilsen 2013 ; Thorup 2000 ; Huang et al. 2017 ; Chen et al. 2022 ) and algorithms ( Holm et al. 2001 ; Huang et al. 2023 ; Henzinger and Thorup 1997 ) have been proposed, we lack an understanding of how these solutions perform in practice. Typical application areas for fully dynamic graphs are simulation scenarios . For instance, power grids are networks with large diameters that include microgrids with smaller diameters. To test the robustness of power grids, islanding techniques ( Goderya et al. 1980 ; Mahat et al. 2008 ) are being used to detect the intentional or unintentional division of a connected power grid into disconnected regions. This is done by simulating the deletion of one or multiple edges and running connectivity queries for each possible set of edge modifications to determine if the power network remains connected. Such simulations crucially depend on fast connectivity algorithms since many possible sets of edge deletions must be performed and checked by running a large number of connectivity queries. To solve the dynamic connectivity problem three classes of solutions, all based on spanning trees, have been proposed (see Section 3 for details). The first class maintains spanning trees without levels. D-trees ( Chen et al. 2022 ) use a heuristic that attempts to minimize the sum of distances between the root and all other nodes in spanning trees, whereas link-cut trees ( Sleator and Tarjan 1985 ) decompose spanning trees into a set of paths and nodes. The second class is based on Euler tour trees ( Henzinger and King 1995 ) , which are balanced binary trees together with a partitioning of the edges into levels, to get the first polylogarithmic time bound for deleting edges ( Henzinger and King 1999 ) . The third category are height-bounded trees to improve the time bounds of balanced binary trees. Height-bounded trees come in two variants: structural trees ( Thorup 2000 ; Wulff-Nilsen 2013 ) are k -ary trees ( k not being constrained) while local trees ( Thorup 2000 ; Huang et al. 2017 ; Wulff-Nilsen 2013 ; Huang et al. 2023 ) are binary trees based on rank trees. In this empirical study we comprehensively evaluate the performance of solutions for the dynamic connectivity problem. Our goal is to understand the tradeoffs along three main dimensions. The first dimension is the balancedness of spanning trees. Balanced trees provide guarantees for the performance of operations but do not allow to directly represent the edges of the graph by edges of the spanning tree since the organization of the nodes in the spanning tree is determined by the balancedness criteria. This leads to a non-negligible overhead for balanced trees. The second dimension is a partitioned representation of spanning trees. A partitioning of the nodes and edges into multiple levels yields faster operations per level but additional data structures are needed to support the partitioning and the construction and maintenance of the partitioning when the graph changes are expensive. The third dimension are space- versus deletion-efficient data structures and algorithms. The most time-consuming spanning tree operation is the deletion of an edge that breaks a component into two components. In this case it must be checked if a replacement edge exists that reconnects the two components. Deletion-efficient data structures focus on solutions to improve the worst case performance of such deletions by introducing auxiliary data structures and considering amortized costs. While the approaches successfully curb the worst case performance and the amortized costs for some classes of workloads they come with hefty overheads. Space-efficient data structures (D-tree, LCT, ST) trade worst case guarantees for lightweight data structures and algorithms. We find that so far no solution achieves a good trade-off among memory footprints, tree heights and maintenance cost. We provide the first comprehensive experimental study for all major data structures for connectivity queries to guide future research on this topic. Our main technical contributions can be summarized as follows: • We implement all major data structures for the dynamic connectivity problem: D-tree, link-cut tree LCT, HK, HKS (a simplified version of HK), HDT, structural tree ST, a variant STV of structural trees, local tree LT, a variant LTV of local trees, and lazy local trees LzT. We provide reference implementations for all solutions, some of which have never been implemented before. • We extensively evaluate all major data structures on large real-world and synthetic graphs with a wide range of workloads. We generate workloads that decouple the dependency between the insertion and deletion of edges to permit a fine-grained control of the growth rate of the graph, and show that lazy local trees with the lowest amortized costs are the slowest in terms of empirically determined runtime. • We leverage our insights from extensive implementations and evaluations to offer lessons learned and we provide recommendations for future work

Read the complete text