Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

Anders Aamand, Adam Karczmarz, Jakub Łącki, Nikos ParotsidisarXiv 2023 · DOI · arXiv

TL;DR

This paper introduces a new dynamic algorithm for maintaining connected and 2-edge-connected components in graphs undergoing edge deletions. It achieves an optimal total time of O(m + n poly log n) for processing edge deletions, with constant-time queries, significantly improving upon previous algorithms for non-sparse graphs.

What Problem Does This Paper Address?

The paper tackles the challenge of efficiently tracking connectivity in large, dynamic graphs where edges are only removed (decremental setting). Specifically, it focuses on maintaining connected components (where vertices are linked by at least one path) and 2-edge-connected components (where vertices are linked by at least two edge-disjoint paths). Existing algorithms for this problem, especially for non-sparse graphs (graphs with many edges relative to vertices), were not optimal in terms of total time complexity. The goal is to achieve a near-linear total time for all edge deletions, allowing for fast queries about connectivity.

Methods

The core of the paper's contribution lies in a novel randomized reduction from decremental c-edge-connectivity to a variant of fully-dynamic c-edge-connectivity on a sparse graph. This reduction is designed to be efficient, with a low cost per edge. The authors introduce a new type of "c-certificate" for graphs, which is a sparse subgraph that preserves the graph's connectivity properties. This certificate is maintained under edge deletions using a combination of techniques:

  • Monte Carlo Randomization: The algorithms are randomized, meaning they provide correct answers with high probability.
  • Decremental Maintenance: The focus is on handling edge deletions efficiently.
  • Sparse Certificate: A key idea is to maintain a sparse representation (the c-certificate) of the graph that captures its connectivity. This certificate is updated when edges are deleted from the original graph.
  • Reduction to Fully-Dynamic Problems: The problem is reduced to solving a related, but potentially simpler, fully-dynamic connectivity problem on the sparse certificate.
  • Self-Check Capability: A crucial feature is a final "self-check" mechanism that allows the algorithm to deterministically verify its correctness after all updates, turning Monte Carlo guarantees into Las Vegas guarantees for certain applications.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Optimal Linear Time for Non-Sparse Graphs: The paper achieves a breakthrough by providing an algorithm that runs in optimal linear total time for edge deletions in non-sparse graphs, a significant improvement over previous bounds that were only linear for very dense graphs.
  • New c-Certificate Construction: The authors introduce a novel randomized c-certificate that is more robust to edge deletions and requires significantly fewer random bits than previous constructions.
  • Amortized vs. Worst-Case: The results focus on amortized update times, which are crucial for dynamic algorithms, and highlight the trade-offs between amortized and worst-case bounds.
  • Self-Check for Robustness: The inclusion of a final self-check mechanism is a powerful feature, enabling static algorithms to leverage dynamic subroutines with high confidence.

Key Results

  • Decremental Connectivity and 2-Edge-Connectivity: The paper presents Monte Carlo randomized algorithms for maintaining connected and 2-edge-connected components.
  • For non-sparse graphs (m = Ω(n poly log n) edges), the total time for processing edge deletions is O(m + n poly log n), with constant-time queries.
  • This improves upon Thorup's [J.Alg. 1999] O(mlog(n²/m) + n poly log n) time algorithm.
  • Low Randomness Requirement: The new algorithms require only O(poly log n) random bits, a significant reduction compared to previous methods.
  • Las Vegas Guarantee: The self-check feature allows for Las Vegas algorithms, which are always correct and terminate with high probability.

Limitations and Future Work

  • Monte Carlo Nature: While the self-check mitigates this, the core algorithms are Monte Carlo randomized, meaning there's a small probability of error if the self-check fails.
  • Focus on Edge Deletions: The primary focus is on decremental connectivity. Extending these results to fully dynamic scenarios (edge insertions and deletions) might require further work.
  • Specific Graph Classes: While the results are general for non-sparse graphs, the paper mentions extensions to specific sparse graph classes (planar, minor-free) in related work. Further exploration of these connections could be fruitful.

Summary updated

Abstract

A classical problem in computational geometry and graph algorithms is: given a dynamic set 𝒮 of geometric shapes in the plane, efficiently maintain the connectivity of the intersection graph of 𝒮. Previous papers studied the setting where, before the updates, the data structure receives some parameter P. Then, updates could insert and delete disks as long as at all times the disks have a diameter that lies in a fixed range [1/P, 1]. As a consequence of that prerequisite, the aspect ratio ψ (i.e. the ratio between the largest and smallest diameter) of the disks would at all times satisfy ψ ≤ P. The state-of-the-art for storing disks in a dynamic connectivity data structure is a data structure that uses O(Pn) space and that has amortized O(P log⁴ n) expected amortized update time. Connectivity queries between disks are supported in O(log n / log log n) time. In the dynamic setting, one wishes for a more flexible data structure in which disks of any diameter may arrive and leave, independent of their diameter, changing the aspect ratio freely. Ideally, the aspect ratio should merely be part of the analysis. We restrict our attention to axis-aligned squares, and study fully-dynamic square intersection graph connectivity. Our result is fully-adaptive to the aspect ratio, spending time proportional to the current aspect ratio ψ, as opposed to some previously given maximum P. Our focus on squares allows us to simplify and streamline the connectivity pipeline from previous work. When n is the number of squares and ψ is the aspect ratio after insertion (or before deletion), our data structure answers connectivity queries in O(log n / log log n) time. We can update connectivity information in O(ψ log⁴ n + log⁶ n) amortized time. We also improve space usage from O(P ⋅ n log n) to O(n log³ n log ψ) - while generalizing to a fully-adaptive aspect ratio - which yields a space usage that is near-linear in n for any polynomially bounded ψ.
BibTeX
@misc{aamand2023fully,
  author = {Anders Aamand and Adam Karczmarz and Jakub Łącki and Nikos Parotsidis},
  title = {{Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs}},
  year = {2023},
  eprint = {2111.09376},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.09376},
}
Figure