PaperlayerView exact revision on arXiv

Source-linked AI summary

Dynamic Connectivity, Minimum Spanning Tree, and 2-Edge Connectivity with Polylogarithmic Worst-Case Update Time

Simon Meierhans, Maximilian Probst Gutenberg, Yu-Cheng Yeh

arXiv:2610.00491v1cs.DS

TL;DR

Fully dynamic connectivity, MST, and 2-edge connectivity still faced sub-polynomial worst-case update bounds for MST and 2-edge connectivity. The paper uses algorithms whose only randomized component is static expander decomposition, and achieves eO(1) worst-case update time against an adaptive adversary with high probability.

  • Problem

    The fastest algorithms for MST and 2-edge connectivity still require sub-polynomial worst-case update time.

    Source: §1 · p. 3

  • Method

    The algorithms use static expander decompositions as their only randomized component.

    Source: §1 · p. 3

  • Results

    eO(1) worst-case update time for fully dynamic connectivity, MST, and 2-edge connectivity, with randomized algorithms that withstand an adaptive adversary and succeed with high probability at each update.

    Source: §1 · p. 3

  • Takeaways & Limitations

    A deterministic algorithm for static expander decomposition would directly derandomize all three algorithms, a reduction novel even for connectivity.

    Source: §1 · p. 3

    The bridge-persistence statement for an edge that loses 2-edge connectivity in its expander applies because the graph is decremental.

    Source: §5.1 · p. 20

Abstract

from arXiv · show

We give fully dynamic algorithms for maintaining connectivity, minimum spanning tree, and $2$-edge connectivity of a graph with worst-case polylogarithmic update time. Our algorithms are randomized and succeed with high probability against an adaptive adversary. For the minimum spanning tree and $2$-edge connectivity problems, this improves over the subpolynomial update time bounds obtained by Nanongkai, Saranurak, and Wulff-Nilsen [FOCS'17], Jin and Sun [FOCS'21], and Jin, Sun, and Thorup [SODA'24], respectively. The only randomized component of our algorithms is the computation of static expander decompositions, and a deterministic algorithm for said problem would directly imply deterministic algorithms for all three problems. This reduction is novel even for the connectivity problem.

1 Introduction

The paper gives fully dynamic algorithms for connectivity, minimum spanning tree, and 2-edge connectivity with eO(1) worst-case update time, randomized against an adaptive adversary. It frames this result against replacement-edge, hierarchy, and coverage-maintenance challenges in prior work.

1.1 Previous Work

  • Connectivity algorithms maintain a maximal spanning forest and must find a replacement edge, or certify none exists, after a forest-edge deletion.Prior polylogarithmic approaches use uniform subsampling or a spanning tree on an expander [MG26].Source: §1 · p. 3, §1.1 · p. 4

1 Introduction

  • eO(1) worst-case update time is achieved for fully dynamic connectivity, minimum spanning tree, and 2-edge connectivity.The algorithms are randomized, withstand an adaptive adversary, and succeed with high probability at each update.Source: §1 · p. 3
  • Static expander decomposition is the algorithms’ only randomized component, so a deterministic algorithm for it would derandomize all three.The reduction is novel even for connectivity.Source: §1 · p. 3

1.1 Previous Work

  • For MST, the paper decouples expander decompositions from its hierarchy to obtain low recourse and avoid snowballing that forces sub-logarithmic hierarchy depth [WN17].The passage identifies that low recourse as necessary to avoid update times that are typically sub-polynomial.Source: §1.1 · p. 4
  • In 2-edge connectivity, high-congestion tree edges force many off-tree edges to be re-embedded after replacement, defeating worst-case control by amortization alone.Earlier vertex sparsifiers can incur (super-)logarithmic recourse per hierarchy level, forcing sub-logarithmic depth [JST24].Source: §1.1 · p. 4
  • The paper combines expander decomposition with coverage maintenance inside expanders, where high-congestion coverage need not be maintained explicitly.Boundary-edge coverage information can be deferred to the next hierarchy level and re-incorporated with polylogarithmic worst-case update time.Source: §1.1 · pp. 4–5
  • For broader dynamic connectivity questions, prior work gives sub-polynomial worst-case updates for pairwise c-edge connectivity and restricted or approximate global mincut, while polylogarithmic worst-case biconnectivity remains open.The cited biconnectivity algorithms are amortized, and no sub-polynomial worst-case algorithm is reported in the passage.Source: §1.1 · p. 5

2 Overview

The overview builds dynamic algorithms from sparsifiers organized in a hierarchy. For MST, it sparsifies by weight and uses expander decompositions to maintain stable components; for 2-edge connectivity, it tracks coverage and removes certified non-bridges while preserving connectivity information.

2 Overview

  • The core-graph framework interleaves dynamic edge and vertex sparsification in geometrically shrinking graphs, and vertex sparsifiers extend naturally from connectivity to MST and 2-edge connectivity.Smaller graphs can be reinitialized more frequently; standard techniques de-amortize these reinitializations.Source: §2 · p. 5

2.1 Dynamic Edge Sparsifier for Minimum Spanning Tree

  • An edge in the high-weight bucket can belong to the MST only if it crosses components of the low-weight graph, motivating selective retention rather than approximate weight bucketing.Naive weight bucketing gives only a (1 + ε)-approximate MST, while this approach aims to preserve the exact MST.Source: §2.1 · p. 6
  • In balanced rounds, peeling a c/log^2 n fraction of highest-weight edges and retaining crossing edges yields an MST sparsifier containing at most a c fraction of the original edges.Rounds continue on components of at most half the vertices until they become singletons.Source: §2.1 · p. 7
  • In an unbalanced round, the sparsifier recurses on the largest component and keeps only each smaller-side vertex’s cheapest edge to it, adding at most n log n edges overall.The retained cheapest edges include every high-weight cut edge that could belong to the MST.Source: §2.1 · p. 7
  • Expander decompositions replace unstable connected components; boundary edges are added to the sparsifier, while pruning preserves relevant MST edges after deletions.The method maintains the sparsifier so that only graph deletions remove its edges, with only eO(1) edges added per update from pruning and hierarchy changes.Source: §2.1 · pp. 8–9
  • The MST hierarchy uses sparse graphs and core graphs to control size and update cost, while background precomputation spreads costly rebuilds across updates for worst-case guarantees.Contracting logarithmically sized components improves sparsity to m/16 + n − 1; core graphs reduce high-index layers to the number of off-tree edges.Source: §2.1 · pp. 9–10

2.2 Dynamic Edge Sparsifier for 2-Edge Connectivity

  • For 2-edge connectivity, tree edges are classified as volume-covered when both sides are large, cut-covered when a small-side cut edge covers them, or bridges otherwise.The volume threshold is 2/ϕ; cut coverage also bounds congestion by 2/ϕ.Source: §2.2 · p. 11
  • The 2-edge sparsifier removes certified non-bridges and replaces them with a spanning forest, preserving 2-edge-connectivity information while bounding its size by n − 1 + |Erest|.The expander decomposition leaves fewer than m/16 inter-cluster edges in Erest.Source: §2.2 · pp. 11–12

3 Preliminaries

This section establishes graph and dynamic-update notation, then introduces expander decompositions and pruning as tools for maintaining connectivity information.

3 Preliminaries

  • The notation defines graphs by vertex and edge sets, uses degree for incident-edge count, and denotes induced subgraphs and edge cuts explicitly.The volume of a vertex set is the sum of its vertices’ degrees.Source: §3 · pp. 12–13
  • A connected component is a maximal connected vertex set; a maximal spanning forest has |V| minus the number of components edges, and the minimum spanning forest is its minimum-weight form.The edge weights are assumed unique, making the minimum spanning forest unique.Source: §3 · pp. 12–13
  • Dynamic graphs change edge sets over time; insertion-only and deletion-only sequences are incremental and decremental, respectively.G(t) denotes the graph after the t-th update.Source: §3 · p. 13
  • Expanders support connectivity maintenance because most of their edges are not bridges, so only a small number need explicit bridge checks.The decomposition algorithm computes a ϕ-expander decomposition of quality O(log^3 m) with high probability.Source: §3 · p. 13
  • A ϕ-expander decomposition partitions vertices into expander components while limiting the number of crossing edges.Its quality q bounds crossing edges by q · ϕ · |E|.Source: §3 · p. 13
  • Expander pruning maintains a set of edges P, adding at most γ ϕ^2 edges per deletion under the stated deletion bound.The expander-deletion setting and γ condition are specified in the lemma statement.Source: §3 · p. 13

4 An Edge-Sparsifier for Fully-Dynamic Minimum Spanning Forest

This section develops a decremental edge sparsifier for minimum spanning forests, using recursive construction and maintenance to preserve the MSF under deletions. Its proof partitions the tree into small chunks with shattering forests, contracts them to reduce the graph, and handles expander-decomposition failures by maintaining component connectivity.

4 An Edge-Sparsifier for Fully-Dynamic Minimum Spanning Forest

  • The decremental sparsifier initializes in O~(m), processes updates in O~(1) time, and explicitly reports its high-probability failures.The algorithm succeeds with high probability.Source: §4 · pp. 13–14

4.1 Constructing the Initial Sparsifier

  • The initial recursive sparsifier preserves MSF(G) exactly and contains at most m/32 + n log2 n edges.The construction removes edges that cannot belong to the MSF.Source: §4.1 · p. 15

4.1.1 Processing Edge Deletions

  • After each deletion, H remains a subgraph with MSF(H) = MSF(G) and gains at most O~(1) edges.The maintenance uses expander pruning and additional edge additions to preserve the invariant.Source: §4.1.1 · p. 17

4.2 Bounding the Required Time for Initialization and Updates

  • Initialization takes O~(m) time, and each edge deletion can be processed in O~(1) time.The bounds include constructing H and initializing the pruning and heap data structures.Source: §4.2 · p. 18

4.3 Proof of Theorem 4.1

  • For m < 32·n log2 n, replace each degree-D>3 vertex with D vertices, assign each one incident edge, and join them by a path of −∞-weight edges; contracting these edges preserves the MST, with n′≤3m and m′≤3m.Source: §4.3 · pp. 18–19
  • A shattering forest partitions all vertices into trees whose volume in H is at most κ, enabling the MST to be divided into small chunks for contraction.The proof splits the degree-3 MST into components, contracts them, runs the sparsifier algorithm on the smaller graph, then uncontracts; each component touched by an update adds eO(1) incident edges.Source: §4.3 · p. 19
  • When an expander-decomposition component may become disconnected, the algorithm maintains its connectivity using [MG26] to prevent an improper MST sparsifier.Too many crossing edges are detected immediately; if the decomposition is derandomized, the connectivity-maintenance step is unnecessary.Source: §4.3 · p. 19
  • The expander-decomposition step is the only stated source of failure: a deficient decomposition can leave a component non-expanding, while excess crossing edges are detected immediately.A component becoming disconnected is the failure mode that could prevent the algorithm from returning a proper MST sparsifier.Source: §4.3 · p. 19

5 An Edge-Sparsifier for Fully-Dynamic 2-Edge Connectivity

This section introduces a decremental edge sparsifier as a key primitive for fully dynamic 2-edge connectivity, maintaining a small subgraph and known non-bridges while preserving the ability to determine whether other edges are bridges. It bounds the sparsifier’s recourse and update time and gives an initial edge-count bound.

5 An Edge-Sparsifier for Fully-Dynamic 2-Edge Connectivity

  • The sparsifier H contains a maximal spanning forest, starts with at most n − (#connected components of G(0)) + m/16 edges, and adds at most eO(1) edges per deletion.Initialization takes eO(m) time; each update takes eO(1) time, and the algorithm succeeds with high probability.Source: §5 · p. 20

5.1 The Algorithm

  • The algorithm forms H from G minus N together with a minimum spanning forest of G intersected with N, and identifies non-bridges within expanders using covered edges.An edge is covered when it is outside the forest or is volume-covered or cut-covered.Source: §5.1 · pp. 20–21

5.2.1 Correctness

  • For edges placed in N, the correctness proof establishes that their endpoints remain 2-edge connected in G.The analysis also proves that edges outside N have the same 2-edge connectivity status in G and H.Source: §5.2.1 · p. 22
  • For edges outside N, endpoint 2-edge connectivity in G is equivalent to endpoint 2-edge connectivity in H; edges in N are 2-edge connected in G.The maintained set N is decremental and has at most eO(1) edges removed per deletion.Source: §5 · p. 20, §5.2.1 · p. 22

5.2.2 Recourse Analysis

  • The recourse analysis shows that a deletion changes the covering status of at most eO(1) edges in each expander.It uses bounds showing that only eO(1) vertices have small subtrees affected by a single measure-coordinate or forest-edge change.Source: §5.2.2 · p. 23
  • At most eO(1) edges change covering status per update, so at most eO(1) edges are removed from N; only such edges can become bridges.Source: §5.2.2 · p. 24
  • Initially, |E(H(0))| ≤ n − (#connected components of G(0)) + m/16, and each deletion adds at most eO(1) new edges to H.Source: §5.2.2 · p. 25
  • Initialization takes eO(m), each edge update to G takes worst-case eO(1), and the algorithm succeeds with high probability.Source: §5.2.2 · p. 25

6 Fully-Dynamic Algorithms via Edge Sparsifiers

This section develops fully dynamic algorithms for connectivity, minimum spanning forest, and 2-edge connectivity with eO(1) worst-case update time; they are randomized and succeed with high probability against adaptive adversaries. For 2-edge connectivity, the update strategy maintains mass through paths in FΛ, ensuring each update is along a tree path and takes eO(1) worst-case time.

6 Fully-Dynamic Algorithms via Edge Sparsifiers

  • The algorithms maintain connectivity, minimum spanning forest, and 2-edge connectivity with eO(1) worst-case update time, succeeding with high probability against adaptive adversaries.The connectivity and minimum spanning forest algorithms report failure when it occurs.Source: §6 · p. 26

6.1 Fully-Dynamic Minimum Spanning Tree

  • In 6.1, a layered sparsification framework maintains FΛ as a minimum spanning forest, with periodic rebuilds de-amortized to worst-case eO(1) updates.The framework combines edge sparsification with vertex sparsification by contracting paths to off-forest edges; rebuilds are performed in the background.Source: §6.1 · pp. 29–30

6.2 Fully-Dynamic 2-Edge Connectivity

  • In 6.2, the framework uses nested spanning forests and the 2-edge-connectivity sparsifier, while preserving the invariant and runtime analysis.At each layer, the forest extends the preceding layer’s forest, so F0 ⊆ F1 ⊆ … ⊆ FΛ.Source: §6.2 · p. 30
  • Non-bridge information from sparsifiers covers corresponding forest paths, allowing 2-edge-connectivity queries to test whether every edge on a forest path is covered.The graph is 2-edge connected exactly when it is connected and every edge in FΛ is covered; vertex-pair queries use the same coverage test along their path.Source: §6.2 · pp. 30–31
  • The 2-edge-connectivity algorithm has eO(m) initialization time and eO(1) worst-case update and query time, succeeding with high probability against an adaptive adversary.The link-cut tree maintains coverage information and supports path coverage updates and queries in eO(1) worst-case time.Source: §6.2 · p. 31
  • The strategy first processes the graph update in other data structures, then identifies edges removed from Ni on each layer and updates their corresponding paths or edges in FΛ.It processes updates to FΛ afterward, before adding mass along paths for edges that joined Ni.Source: §6.2 · p. 31
  • Only eO(1) edges are removed from Ni across the layers, and the strategy processes only one edge change in FΛ.Mass is removed from corresponding paths or edges for removed edges, then added along x-to-y paths for edges e = xy that joined Ni.Source: §6.2 · p. 31
  • Because every update is along a tree path in FΛ, it can be processed in eO(1) worst-case update time.Source: §6.2 · p. 31

A Proofs of the centroid properties

Two centroid claims bound by eO(1) the small subtrees affected by a unit measure change or a forest edge update; these claims support the recourse analysis of the 2-edge connectivity sparsifier.

Claim 5.9

Claim 5.9 proof

  • For a unit measure change, affected light subtrees lie on the changed vertex’s path to the centroid, and the nested subtrees’ measure threshold bounds their number.For a decrease, subtrees at or below 2γ/ϕ retain their tree structure; an increase uses almost identical reasoning.Source: A Proofs of the centroid properties · p. 36

Claim 5.10

Claim 5.10 proof

  • Deleting an edge splits its component into two, and symmetry lets the proof bound affected vertices on one side to establish the overall bound.Other components are unaffected by the deletion.Source: A Proofs of the centroid properties · p. 37
  • For an edge insertion, affected vertices lie on the endpoint-to-centroid path, where nesting and the 2γ/ϕ threshold limit their number to 2γ/ϕ.The argument uses a laminar family of subtrees and their accumulated measure.Source: A Proofs of the centroid properties · p. 37
Loading 2610.00491v1…