Module polylog 

Polylogarithmic Worst-Case Dynamic Connectivity

Implementation based on “Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time” (arXiv:2510.08297, October 2025).

Key Innovation

Uses the core graph framework with a hierarchy interleaving vertex and edge sparsification to achieve O(polylog n) expected worst-case update time.

Time Complexity

• Insert: O(log³ n) expected worst-case
• Delete: O(log³ n) expected worst-case
• Query: O(log n) worst-case

Algorithm Overview

1. Maintain a hierarchy of O(log n) levels
2. Each level i contains edges of “level” ≥ i
3. Use edge sparsification via low-congestion shortcuts
4. Rebuild levels incrementally to avoid worst-case spikes

Structs

PolylogConnectivity

Polylogarithmic worst-case dynamic connectivity

PolylogStats

Statistics for polylog connectivity