Source-linked AI summary
Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition
Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak, Haoze Wang
TL;DR
The paper asks whether low-degree Steiner forest decompositions can be computed with constant degree in near-linear time. It allows the forest to contain excluded vertices and gives a simple deterministic construction, yielding a deterministic connectivity oracle under vertex failures with the stated space, preprocessing, update, and query bounds.
Problem
The central question is whether a low-degree Steiner forest decomposition with degree O(1) can be computed in near-linear time.
Method
The paper allows the forest to contain vertices in X and uses a simple deterministic algorithm that computes a maximum-degree-4 decomposition in O((m + n)α(n)) time.
Results
The resulting deterministic d⋆-vertex-failure connectivity oracle uses O(m log3 n) space, O(d⋆m log3 n) preprocessing time, O(d2 log3 n log4(d log n)) update time, and O(d) query time.
Takeaways & Limitations
The relaxed decomposition is strong enough to yield a connectivity oracle and supports an almost truly linear-time construction with an optimal constant degree bound.
Takeaways & Limitations
The connectivity-oracle construction uses the framework of [LS22] as a black box.
Abstract
from arXiv · showhide
We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of size at most $|U|/2$ and a forest $T\subseteq G-X$ of maximum degree $Δ$ such that, for every connected component $C$ of $G-X$, some connected component of $T$ contains all terminals in $U\cap V(C)$. This is the central decomposition behind several connectivity oracles under vertex failures [DP20, LS22, LW24]. The state-of-the-art algorithms either take $O(mn\log n)$ time with degree bound $4$ [DP20], or take $m^{1+o(1)}$ time with the weaker degree bound $O(\log^{2}n)$ [LW24]. We show that if $T$ is allowed to contain vertices of $X$, then a degree-$4$ decomposition can be computed by a very simple algorithm in $O(mα(n))$ time. Further, we show that this relaxed decomposition is equally useful for constructing connectivity oracles under vertex failures. As a consequence, we obtain a deterministic connectivity oracle under $d$ vertex failures with $\tilde{O}(m)$ space, $\tilde{O}(md_\star)$ preprocessing time ($d_\star$ is an upper bound on the number of failed vertices), $\tilde{O}(d^{2})$ update time, and $O(d)$ query time. Up to polylogarithmic factors, this oracle strictly improves all known oracles; in particular, it removes the $n^{o(1)}$ factors from the preprocessing and update times of [LS22, LW24].
1 Introduction
The paper asks whether constant-degree Steiner forest decompositions can be computed near-linearly, and answers yes by allowing certifying trees to include removed vertices. This yields a faster connectivity oracle under vertex failures with improved preprocessing and update guarantees.
- Motivation: Low-degree forests certify connectivity robustly under vertex failures, but a low-degree Steiner tree spanning arbitrary terminals may not exist.Deleting d vertices from a maximum-degree-Δ tree creates at most 1+Δd components.
- Motivation: The standard decomposition removes X with |X|≤|U|/2 and builds a bounded-degree forest certifying all terminals within each component of G−X.This decomposition supports several connectivity oracles and recursive handling of X.
- Prior Work: Previous algorithms achieved degree 4 in O(mn log n) time or m1+o(1) time with degree O(log2 n), motivating the constant-degree near-linear-time question.The earlier approaches rely on minimum-degree Steiner-tree approximation or cut-matching frameworks.
- Our Result: Allowing the forest T to contain vertices of X enables a simple deterministic degree-4 decomposition in O((m+n)α(n)) time.The resulting weak decomposition still certifies terminals in every component of G−X.
- Connectivity Oracle: The decomposition integrates with the [LS22] framework to remove subpolynomial factors from connectivity-oracle preprocessing and update times.The paper constructs a deterministic oracle with O(m log3 n) space, O(d⋆m log3 n) preprocessing, O(d2 log3 n log4(d log n)) update, and O(d) query time.
2 Simple Weak Low-Degree Steiner Forest Decomposition
The paper presents a simple deterministic algorithm that builds a weak degree-4 Steiner forest decomposition by repeatedly adding linking paths, then removes degree-4 vertices. Its implementation runs in O((m+n)α(n)) time and satisfies the required size and connectivity properties.
- 2.1 Algorithm Description: The algorithm initializes T with one isolated vertex per terminal and repeatedly connects distinct components using linking paths whose endpoints have degree at most 3.Each linking path has internal vertices outside the current forest.
- 2.1 Algorithm Description: The algorithm returns X as the vertices of degree 4 in T, guaranteeing |X| ≤ |U|/2 because every leaf remains a terminal.In any degree-4 forest, the number of degree-4 vertices is at most half the number of leaves.
- 2.2 Correctness: For every component C of G−X containing terminals, at most one component of T intersects C, so that component spans all terminals in U∩V(C).If two forest components intersected C, a shortest path between them would be a remaining linking path.
- 2.3 Implementation Details: The implementation maintains active vertices, the active subgraph, a disjoint-set structure for T, and candidate boundary edges processed in rounds.A round either adds a linking path or deletes vertices from the active subgraph.
- 2.3.1 Running Time of the Implementation: The total running time is O((m+n)α(n)), with O(mα(n)) time for scanning boundary edges and all DFS calls.Each active vertex is scanned at most once, and only O(m) boundary-edge candidates are processed.
- 2.3.2 Correctness of the Implementation: The correctness proof establishes that no linking path remains when the algorithm terminates.The DFS-tree analysis shows that any remaining linking path would have caused an internal vertex to be added to T.
3 Optimal Low-Degree Hierarchy
The paper constructs an optimal low-degree hierarchy by repeatedly applying the weak decomposition to residual terminal sets. The resulting hierarchy has degree parameter 4, depth O(log n), and near-linear construction time.
- Hierarchy Definition: A low-degree hierarchy organizes vertex-induced, pairwise-disjoint components into a laminar sequence across levels.Each component has a unique parent at the next level, and the final level contains G.
- Hierarchy Definition: At each level, the terminal set consists of vertices in a component that belong to none of its children, and each T_i is a Steiner forest for that level.The forest is taken with respect to G−U>i and has bounded maximum degree.
- Construction: The resulting hierarchy has depth O(log n) and degree parameter 4, constructed deterministically in O(mα(n) log n) time.This is the stated guarantee of Theorem 3.2.
- Construction: The construction strictly subsumes prior low-degree hierarchy constructions and achieves optimal parameters because constant degree requires Ω(log n) depth.The degree-depth trade-off is stated as optimal up to the theorem’s parameters.
- Construction: The construction starts with X_1=V and repeatedly applies CutTreePair(G,X_i) until some X_{i⋆+1} is empty.After at most 1+⌈log_2 n⌉ calls, the process terminates and defines the hierarchy depth.
- Analysis: The hierarchy uses the inclusion and enlargement properties of Steiner forests to transfer guarantees from X_i to the level terminals U_i and excluded sets U>i.These transfers follow from the observation that shrinking terminal sets or enlarging excluded vertex sets preserves the Steiner-forest property.
4 Connectivity Oracles under Vertex Failures
The section combines the new low-degree hierarchy with connectivity-oracle frameworks and derives deterministic vertex-failure oracles with explicit space, preprocessing, update, and query bounds.
- The known [LS22] framework is used as a black box to combine the new hierarchy with connectivity-oracle data structures.
- O(mα(n) log n) preprocessing constructs the hierarchy, while the remaining structures yield total O(d⋆m log3 n) preprocessing time and O(m log3 n) space.
- The resulting oracle answers queries in O(d) time and updates a failure set using d2 log3 n log4(d log n) time.
- The simpler -based oracle uses O(d⋆m log2 n) space and preprocessing time, O(d2(log2 n)(d2 ⋆+ log2 n)) update time, and O(d + log log n) query time.
- The construction represents hierarchy tree copies in an auxiliary graph and reconnects affected subtrees after failures using Euler-tour structures and range reporting.
- For surviving terminal copies, connectivity in the reconstructed graph R is equivalent to connectivity of the corresponding original vertices in G−D.
A Optimality of Our Low-Degree Hierarchy
The paper proves that low-degree hierarchy parameters obey an inherent degree-depth trade-off, establishing optimality for its constant-degree, logarithmic-depth construction.
- For any k ≥2 and ℓ≥1, some graph with n = Θ(kℓ) nodes requires maximum degree at least k or hierarchy depth at least ℓ.
- The lower bound follows from recursively constructed graphs whose branching factor and depth force this degree-depth alternative.
- Theorem A.2 states that every hierarchy satisfies (s(n) + 1)p(n)+1 = Ω(n) and therefore p(n)·log(s(n)) = Ω(log n).
- Any construction with an O(1) degree parameter must have depth at least Ω(log n), matching the hierarchy’s O(log n) depth.
A.1 Proof of Lemma A.1
The proof constructs recursively branching graphs and shows that any hierarchy with degree below the branching factor must have depth at least the recursion depth.
- G0 is a single root, and each Gi is formed recursively from copies of Gi−1 connected to a new root ri.
- The resulting graph G = Gℓ has kℓ+kℓ−1+· · ·+1 = Θ(kℓ) nodes.
- When the hierarchy degree parameter satisfies s < k, the construction forces hierarchy depth at least ℓ.
- Figure 2 illustrates the first two recursively constructed graphs, G1 and G2, for k = 3.
B Pseudocode of the Implementation of Theorem 1.1
The implementation initializes a terminal forest and repeatedly searches for linking paths, using DFS and disjoint-set updates to maintain the decomposition efficiently.
- The algorithm initializes T with isolated terminal vertices, scans terminal neighbors, and processes a pending edge set Eb until it is empty.
- When low-degree endpoints lie in distinct forest components, the algorithm adds their connecting edge as a linking path and updates Eb and the disjoint-set structure.
- When a low-degree terminal endpoint reaches an active vertex, DFS recursively explores unvisited neighbors while tracking the current visited set W.
- After each DFS, visited vertices are removed from Va and the graph and disjoint-set structures are updated; the algorithm then returns (X,T).
- A successful DFS produces a path from the DFS root through the explored path to a qualifying neighbor, which is added to T.