PaperlayerView exact revision on arXiv

Source-linked AI summary

Incremental Exact Vertex Connectivity

Felix Adena, Monika Henzinger, Christoph Kern, Daniel Rutschmann

arXiv:2610.21531v1cs.DS

TL;DR

Dynamic vertex connectivity lacks fast insertion-only algorithms beyond small connectivity values, and prior conditional lower bounds leave important settings uncovered. This paper gives parameterized incremental algorithms and an OMv-based lower bound. The algorithm's adversary guarantees and graph scope vary by setting, while the lower bound rules out sublinear amortized updates for κ = Θ(n).

  • Problem

    Dynamic vertex connectivity has limited fast-update results, motivating whether insertion-only or deletion-only algorithms can achieve amortized ˜O(poly(κ)) time.

    Source: §1 · p. 3

  • Method

    The paper develops an incremental vertex-connectivity algorithm and proves conditional lower bounds using the OMv assumption.

    Source: §1 · pp. 3–4

  • Results

    O(κ^4 log^2(n)) amortized insertion time is achieved for undirected graphs against a randomness-adaptive adversary, while OMv rules out O(κ^(3−ε)/m) updates and O(κ^(2−ε)) queries after polynomial preprocessing.

    Source: §1 · pp. 3–4

  • Takeaways & Limitations

    For κ = Θ(n), the conditional lower bound gives O(n^(1−ε)) insertion-time and O(n^(2−ε)) query-time thresholds, while the algorithm also achieves parameterized update bounds.

    Source: §1 · p. 4

    The randomness-adaptive analysis described for this setting works only for undirected graphs, since directed graphs may have exponentially many choices of L and R.

    Source: §5.3 · p. 16

Abstract

from arXiv · show

We study the problem of maintaining the vertex connectivity $\kappa$ of a graph under edge insertions. For undirected graphs, our algorithm uses $O(\kappa^4 \log^2 n)$ amortized time per edge insertion. After each edge insertion, the algorithm outputs the current value of $\kappa$, plus a set of $\kappa$ vertices whose removal disconnects the graph. Our algorithm is Monte-Carlo randomized and works with a randomness-adaptive adversary. The algorithm also works on directed graphs against an oblivious adversary, which is equivalent to an output-adaptive adversary if we only have to output the current value of $\kappa$. Previously, algorithms for maintaining the vertex connectivity with $o(n)$ time per edge insertion were only known for $\kappa \le 2$, and need $\tilde{O}(\log^2 n)$ and $O(\sqrt{n})$ time per edge insertion for $\kappa = 1,2$, respectively. Moreover, for $\kappa > 4$, no algorithm faster than recomputation from scratch was known. We complement our algorithm with a conditional lower bound: Under the OMv conjecture, any insertions-only algorithm that outputs the current value of $\kappa$ after every insertion needs $\Omega(n^{1-\varepsilon})$ amortized time per edge insertion for $\kappa = \Theta(n)$. Previous conditional lower bounds for this problem only apply to worst case running time, or algorithms that support both edge insertions and edge deletions.

1 Introduction

The introduction frames dynamic vertex connectivity as less understood than edge connectivity and asks whether insertion-only or fully dynamic algorithms can achieve faster update times. It presents a parameterized incremental algorithm and an OMv-based conditional lower bound.

1 Introduction

  • The paper asks whether vertex connectivity admits polylogarithmic amortized insertion time, sublinear fully dynamic time, or amortized ˜O(poly(κ)) time in insertion-only or deletion-only settings.For directed graphs, it also asks whether the parameterized bound is possible.Source: §1 · p. 3
  • The algorithm maintains undirected vertex connectivity in O(κ^4 log^2(n)) amortized insertion time against a randomness-adaptive adversary.It can return κ in constant time or a minimum vertex cut in time linear in its size.Source: §1 · p. 3
  • O(κ^3 log^2(n)) amortized insertion time is achieved on directed and undirected graphs against an oblivious adversary, or an output-adaptive adversary when returning only κ.The paper identifies this as the first dynamic algorithm with an amortized bound ˜O(poly(κ)).Source: §1 · p. 4
  • Under the OMv assumption, no insertion-only or deletion-only algorithm supports amortized O(κ^(3−ε)/m) updates and O(κ^(2−ε)) value queries after polynomial preprocessing.For κ = Θ(n), the bounds become O(n^(1−ε)) per update and O(n^(2−ε)) per query.Source: §1 · p. 4
  • The lower bound rules out polylogarithmic-in-n insertion-only vertex-connectivity algorithms independent of κ, contrasting with known polylogarithmic insertion-only edge-connectivity algorithms.The introduction notes that the bound helps explain the lack of progress and that vertex connectivity is more challenging in this respect.Source: §1 · pp. 2, 4

2 Preliminaries

The preliminaries establish graph, cut, and incremental-update notation used throughout the paper. They define vertex connectivity through minimum vertex cuts and describe how directed graph boundaries and volumes are represented.

Graphs and Neighborhoods

  • For disjoint vertex sets S and T, E_G(S,T) denotes directed edges from S to T; in undirected graphs it denotes edges crossing the sets.G\S is the subgraph induced by vertices outside S.Source: §2 · p. 4

Volumes and Boundaries

  • The preliminaries define incoming and outgoing boundaries, neighborhoods, and volumes for vertex sets using the corresponding directed degrees.They assume simple graphs unless stated otherwise and use base-2 logarithms unless specified.Source: §2 · pp. 4–5

Vertex Connectivity and Cuts

  • A vertex cut is a vertex set whose removal leaves a graph not strongly connected or as a single vertex; κ(G) is the minimum cut size.A separation triple (L, S, R) has nonempty L and R and no edges from L to R; when |S| = κ, it is a κ-separation triple.Source: §2 · p. 5

Dynamic Setting

  • In the incremental setting, the graph starts empty or with an initial edge set and receives edge insertions.m denotes the total number of edges after all insertions.Source: §2 · p. 5

3 Overview

The overview builds incremental vertex-connectivity maintenance from cut-volume phases and randomized sampling, then presents an OMv-based lower bound through a matching-to-cut transformation.

3 Overview

  • The algorithm processes insertions in κ-rounds and volume phases, advancing κ after cuts of that size disappear and requiring both graph orientations to become (κ, 2ν)-ready.The phases use geometrically increasing ν values.Source: §3 · pp. 5–6
  • Sampling terminal roots targets every κ-separation triple whose left side has sufficiently large volume, while reversed-graph sampling targets large right sides.The overview adapts a sampling procedure from [Mos26].Source: §3 · pp. 6–7
  • For each root s, IncrementalRootedVC reports an s-rooted cut or certifies none exists, with total running time O(νκ² + ℓ).Its stated conditions include δ+(G) > κ and ν ≤ m/(24κ).Source: §3 · p. 6
  • When the volume threshold is too large for rooted maintenance, O(κ) sampled terminal pairs use incremental max-flow structures to report size-κ cuts.The cited structure has total running time O(κ(m + ℓ)).Source: §3 · p. 7
  • The randomized guarantee extends to directed graphs against an oblivious adversary, but the randomness-adaptive argument is limited to undirected graphs.The directed case may have exponentially many choices for one side of a separation triple, preventing the stated repetition argument.Source: §3 · pp. 6, 9

3.1 Lower Bound Overview

  • For graphs with Θ(n) vertex connectivity, OMv rules out amortized O(n^{1−ε}) update time and O(n^{2−ε}) query time.The reduction’s figure links maximum matching size in G to minimum vertex-cover size in G and minimum vertex-cut size in H.Source: §3.1 · p. 9, Figure 1 · p. 10
  • Under OMv, no algorithm achieves amortized O(κ^{3−ε}/m) update time and O(κ^{2−ε}) query time for any κ.The bound applies to insertions-only or deletions-only algorithms.Source: §3.1 · p. 10

4 Lower Bound Details

The lower-bound construction converts bipartite matching into vertex connectivity by transforming the graph and preserving the relevant optimum. Applying OMv-based matching bounds yields lower bounds for both unrestricted and κ-bounded connectivity.

4 Lower Bound Details

  • The transformation makes each bipartition side, together with an added vertex, a clique; the resulting graph H has vertex connectivity equal to G’s maximum matching size.The construction uses the equality between bipartite maximum matching and minimum vertex-cover size.Source: §4 · pp. 10–11
  • For graphs with Θ(n) vertex connectivity, OMv rules out amortized O(n^{1−ε}) update time and O(n^{2−ε}) query time.The bound covers Θ(n²) operations on Θ(n)-vertex graphs, even when connectivity remains Θ(n).Source: §4 · p. 11
  • For any κ, OMv rules out amortized O(κ^{3−ε}/m) update time and O(κ^{2−ε}) query time.Copies of an added vertex allow Θ(m) operations while keeping connectivity at most κ.Source: §4 · p. 12

5 Analysis of Algorithm 1

This section analyzes Algorithm 1’s running time and correctness, including how repeated sampling establishes readiness and finds vertices on both sides of a separation. It also proves that the line-19 loop terminates only when the graph is (κ + 1)-vertex connected, with probability at least 1 − n^-7 under the stated conditions.

5.1 Running time analysis

  • Over m insertions, total running time is O(mκ^3 log^2 n) against an oblivious adversary and O(mκ^4 log^2 n) against a randomness-adaptive adversary, assuming correct outputs.Source: §5.1 · p. 12

5.2 Correctness

  • Success probability is at least 1−n^-5 with boosts ≥27 log n for directed or undirected oblivious inputs, or ≥κ·(33 log n+288) for undirected randomness-adaptive inputs.Success means outputting a minimum vertex cut after every edge insertion.Source: §5.2 · p. 13

5.3 Proof of Lemma 20

  • Oblivious analysis exploits monotonicity and a longest-lived separation triple; adaptive analysis union-bounds at most n^(κ+1) triples and is limited to undirected graphs.Source: §5.3 · pp. 15–16
  • With boosts ≥27 log n for oblivious or ≥33κ log n for undirected adaptive adversaries, the loop makes G and its reverse (κ, m/(48κ))-ready with probability at least 1−n^-7.Source: §5.3 · pp. 16–18

5.4 Proof of Lemma 21

  • If G and its reverse are (κ, m/(48κ))-ready, sampling finds a pair crossing either orientation of any fixed κ-separation triple with probability at least 1−2^-boosts/3.Source: §5.4 · p. 18
  • For undirected graphs against randomness-adaptive adversaries, boosts ≥ κ(33 log n + 288) ensure every κ-separation triple has a successful sampling iteration with probability at least 1 − n^-7.The argument applies simultaneously to all κ-separation triples when G and its reverse are (κ, m 48κ)-ready.Source: §5.4 · p. 19
  • Under the stated readiness and boost bounds, line 19 terminates only once G is (κ + 1)-vertex connected, with probability at least 1 − n^-7.The bounds are boosts ≥ 27 log n for directed or undirected graphs against an oblivious adversary, and boosts ≥ κ(33 log n + 288) for undirected graphs against a randomness-adaptive adversary; G and its reverse must be (κ, m 48κ)-ready.Source: §5.4 · p. 19
  • When a sampled source-target pair crosses a κ-separation triple, IncrementalMaxFlowVC reports a size-κ vertex cut, so the corresponding loop continues until that triple is no longer valid.The reverse-graph case is handled analogously.Source: §5.4 · p. 20

6 Sampling

The sampling subroutines select roots to hit large-volume vertex sets or sample a vertex to hit one side of a small separation cut. Their stated guarantees provide constant-probability detection.

6 Sampling

  • SampleRoots samples edges uniformly with replacement and returns vertices with sampled outgoing edges, producing a set that hits large-volume vertex sets with constant probability.It uses at most 2m/ν samples and runs in O(m) time.Source: §6 · p. 20
  • The probability that no sampled edge originates from a set A is the probability that A ∩ T is empty.The proof uses this identity to establish the sampling guarantee.Source: §6 · p. 20
  • For any separation triple with |S| = κ ≤ n/2, a uniformly sampled vertex lies in L ∪ R with probability at least 1/2.Since |L ∪ R| = n − |S| ≥ n/2.Source: §6 · p. 20

7 Incremental Rooted Cuts

This section develops incremental algorithms for maintaining small rooted edge cuts and rooted vertex cuts under edge insertions, using a split-graph reduction from vertex cuts to edge cuts. It establishes randomized correctness and total-running-time guarantees, including a probability bound on when the algorithms may stop reporting a cut.

7.1 Edge Cuts

  • The edge-cut algorithm extends [FNYSY20] and generalizes [GK21] by growing a reachability tree incrementally, pausing when it outputs a cut and resuming after an insertion.The incremental reachability structure extends the tree when a newly inserted edge can reach additional vertices.Source: §7 · p. 21, §7.1 · p. 22

7.2 Vertex Cuts

  • Under κ≤n/2, ν≤m/(24κ), and δ+(G)>κ, rooted vertex-cut maintenance takes O(νκ^2 + ℓ) total time and reports a cut for a (κ, ≤6νκ)-separation triple or ⊥.With probability at least 1/2, the data structure reports ⊥ only after a fixed (κ, ≤ν)-separation triple ceases to be valid; the guarantee holds against a randomness-adaptive adversary.Source: §7 · p. 22

7.1 Edge Cuts

  • For ν≤m/(2κ), incremental rooted edge-cut maintenance takes O(νκ^2 + ℓ) total time and reports a (κ, ≤3νκ)-edge cut or ⊥, with probability at least 1/2 not reporting ⊥ while a fixed (κ, ≤ν)-cut remains valid.The guarantee holds against a randomness-adaptive adversary.Source: §7.1 · p. 25

7.2 Vertex Cuts

  • Splitting each non-root vertex into in- and out-copies reduces a rooted (κ, ≤ν)-separation triple to a rooted (κ, ≤2ν)-edge cut, with improved volume-bound constants over prior lemmas.The cut in the split graph consists of the internal edges corresponding to the separator vertices.Source: §7.2 · p. 26
  • The reduction runs IncrementalRootedEC on a split graph, maps vertices whose two copies lie in L′ back to L, and outputs the out-neighborhood N+_G(L) as the separator.Each inserted edge (u, v) becomes (u+, v−); the split graph can be reused across source vertices after edge reversals are undone.Source: §7.2 · pp. 27–28

Correctness.

  • Under κ ≤ n/2 and δ+(G) > κ, Lemma 36 shows the constructed triple (L, N⁺_G(L), V(G)\(L∪N⁺_G(L))) is an s-rooted (κ, ≤6νκ)-separation triple in G; its vertex cut is S = N⁺_G(L).For the theorem’s particular s-rooted (κ, ≤ν)-separation triple, the mapped (κ, ≤2ν)-edge cut in G′ remains valid while the triple does; against a randomness-adaptive adversary, the data structure outputs ⊥ only once the triple is no longer valid, with probability at least 1/2.Source: Correctness · p. 28
  • The implementation maintains the separator efficiently by recording changes to L and applying them only when IncrementalRootedEC outputs L′, when vol+_G(L) ≤ 6νκ.This avoids costly updates while L grows; maintaining S then costs O(νκ) per outer iteration, over at most κ + 1 iterations.Source: Correctness · p. 29

7.2 Vertex Cuts

  • For ℓ insertions, the data structure runs in O(νκ^2 + ℓ) total time; for a specified valid s-rooted (κ, ≤ν)-separation triple, it outputs ⊥ only after validity ends, with probability at least 1/2 against randomness-adaptive adversaries.Source: Correctness · pp. 28–29

8 Auxiliary data structures

The auxiliary structures maintain reachability and strong connectivity under insertions, and maintain exact s-t vertex cuts using incremental max-flow.

8 Auxiliary data structures

  • O(m) total time maintains single-source reachability through insertions by adding newly reachable vertices and processing their outgoing edges.Each edge is processed at most twice, and a counter supports constant-time checks that all vertices are reachable.Source: §8 · p. 29
  • O(m) total time maintains strong connectivity by checking reachability from one fixed vertex in both the graph and its reversal.Strong connectivity holds exactly when every vertex is reachable from the fixed vertex in both copies.Source: §8 · p. 29
  • O(κ(m + ℓ)) total time maintains exact s-t vertex cuts by converting vertex cuts to edge cuts in a split-vertex graph and using incremental max-flow.The structure stops augmenting once flow exceeds κ and outputs the cut after each insertion.Source: §8 · p. 30

9 Declaration of AI usage

The authors state that the research results were obtained without artificial intelligence, while Gemini 3.1 Pro assisted with Fig. 1’s TikZ source and large language models were used for spell-checking.

9 Declaration of AI usage

  • The authors report no AI use in obtaining results, but used Gemini 3.1 Pro for Fig. 1’s TikZ source and large language models for spell-checking.Source: §9 · p. 30
Loading 2610.21531v1…