arXiv preprint ·
Fully Dynamic Triangle and 4-Vertex Subgraph Counting: From Theory to Practice and Back Again
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Counting small patterns is a core primitive in large-scale graph analytics, with numerous applications in data management and network analysis. As modern graphs are massive and continuously evolving, maintaining such counts efficiently under updates is essential. Although specialized dynamic algorithms for patterns with up to four vertices exist, they remain largely theoretical; practitioners instead rely on general-purpose or approximate methods. We present an in-depth study of two dynamic approaches by Eppstein et al. and Hanauer et al. for maintaining counts of triangles and all connected four-vertex subgraph patterns, both based on variants of heavy-light vertex partitioning. We introduce theoretical and practical optimizations and develop hybrid variants that combine complementary strengths of both approaches. Experiments on 56 large real-world and synthetic dynamic graphs show that our optimized algorithms outperform the original methods and strong static and dynamic baselines on nearly all instances, both in total running time and worst-case update time, with speedups of up to several orders of magnitude. We further provide practical guidelines for algorithm selection and tuning. To the best of our knowledge, this is the first comprehensive empirical study of heavy-light partitioning for dynamic subgraph counting, and our findings may inform other algorithms based on this technique.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
Optimal Mixing for Local Edge-Coloring Dynamics on Trees
Optimal Labeling Schemes for $Γ$-Free Matrices
Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
On the Largest Cardinality Subset Sum
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.