Source-linked AI summary
Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
TL;DR
Fully correct EFT connectivity labels for general fault bounds have been an open goal alongside compact randomized schemes. This paper replaces cycle-space sampling with sparse cycle bases to give a deterministic polynomial-time scheme using O(log^2 n)-bit labels. For f = ω(log^2 n), it slightly improves the stated randomized bounds.
Problem
For a general fault bound, it remained open whether EFT connectivity could have eO(1)-size labels that are fully correct across queries.
Source: §1 · p. 2Method
Results
Takeaways & Limitations
The paper gives deterministic polynomial-time EFT connectivity labeling with O(log^2 n)-bit labels for a general fault bound.
Source: §1 · p. 2The preliminaries assume, without loss of generality, that the input graph is simple and connected.
Source: §2 · p. 3
Abstract
from arXiv · showhide
For an undirected graph $G = (V,E)$ and a fault bound $f$, an edge-fault-tolerant connectivity labeling scheme assigns short labels to vertices and edges, so that for any vertex pair $(s,t)$ and failed edge set $F\subseteq E$ with $|F|\leq f$, the connectivity between $s$ and $t$ in $G-F$ can be answered by inspecting only the labels of $s$, $t$ and edges in $F$. In this paper, we present a labeling scheme that uses $O(\log^{2}n)$-bit labels that can be computed in deterministic polynomial time. This improves upon the previous $\tilde{O}(\sqrt{f})$ deterministic bound of [Long, Pettie, Saranurak'25], and even slightly improves the $O(\min\{f+\log n,\log^{2}n\log f\})$ randomized bound of [Dory, Parter'21] and [Long, Pettie, Saranurak'25] when $f = \Omega(\log^{2}n)$. Moreover, for a general $f$, this is the first labeling scheme that produces an $\tilde{O}(1)$-size labeling which is simultaneously correct across all queries. Our approach combines the cycle-space-based labeling scheme from Dory and Parter with a recent result by [Knauer'26] on sparse cycle bases.
1 Introduction
The paper answers whether general fault bounds permit fully correct EFT connectivity labels of near-constant size, giving a deterministic polynomial-time scheme with O(log^2 n)-bit labels. It builds on cycle-space labeling by replacing randomized sampling with sparse cycle bases.
1 Introduction
- An EFT connectivity labeling scheme answers connectivity after edge failures using only the labels of the query vertices and failed edges.Source: §1 · p. 2
Randomized Labeling Schemes
Deterministic Labeling Schemes
Our Results
- O(log^2 n)-bit labels resolve the open question of fully correct EFT connectivity labeling for a general fault bound.The scheme is deterministic and has polynomial-time preprocessing.Source: §1 · p. 2
- For f = ω(log^2 n), the result slightly improves the randomized bounds min{f + log n, log^2 n log f} [DP21] [LPS25].Source: §1 · p. 2
Our Approach
- The scheme replaces cycle-space sampling—the only randomized part of Dory and Parter’s approach—with sparse cycle bases [DP21].Knauer [Kna26] proves that a sparse cycle basis with O(log n) congestion exists, improving the previous O(log^2 n) bound [FH21].Source: §1 · pp. 2–3
2 Preliminaries
The preliminaries assume a simple connected input graph and introduce induced edge cuts and the cycle space. They also state a cycle-basis criterion for recognizing induced cuts.
2 Preliminaries
- The graph is assumed, without loss of generality, to be simple and connected.Source: §2 · p. 3
Induced Edge Cuts
- For a vertex subset S, δ(S) is the set of edges crossing between S and V \\ S, called an induced edge cut.Source: §2 · p. 3
The Cycle Space
3 The Labeling Scheme
The scheme answers edge-failure connectivity queries using O(log^2 n)-bit labels, with deterministic polynomial preprocessing. It replaces cycle-space sampling with sparse cycle bases and encodes the query as a linear feasibility test.
3 The Labeling Scheme
- Sparse cycle bases replace the cycle-space sampling that was the only randomized part of the Dory–Parter scheme.The required basis has O(log n) congestion and can be computed deterministically in polynomial time.Source: §3 · p. 4
3.1 The Linear System Interpretation
- The query is reduced to finding a subset K of failed edges that satisfies the induced-cut constraints and crosses the s-t tree path an odd number of times.A feasible K means s and t are disconnected in G − F.Source: §3.1 · p. 4, §3.2 · p. 5
3.2 The Labels
- Failed-edge labels list the IDs of basis cycles containing each edge, allowing the query to recover the cycle constraints that involve failed edges.Each edge belongs to O(log n) basis cycles, so these IDs contribute O(log^2 n) bits per edge label.Source: §3.2 · p. 5
- Ancestry labels identify whether a failed tree edge lies on the s-t path, using O(log n) bits per label for this information.Non-tree edges do not belong to the tree path.Source: §3.2 · p. 5
3 The Labeling Scheme
- O(log^2 n) bits suffice for each label, with deterministic polynomial preprocessing and query time O(|F|^3 log n).The query reads only the labels of s, t, and the failed edges.Source: §3 · pp. 3–4, §3.2 · p. 5
3.2 The Labels
- Gaussian elimination tests feasibility of the resulting system over F2, with |F| variables and O(|F| log n) constraints.The resulting query time is O(|F|^3 log n).Source: §3.2 · p. 5
4 Algorithmic Sparse Cycle Basis
The section gives a deterministic polynomial-time construction of a cycle basis with O(log n) congestion, using an algorithmic three-step framework. It moves from low weighted-average congestion through MWU to deterministic rounding that preserves a potential bound.
4.2 Fractional Sparse Cycle Bases via MWU
- Given a low-average-congestion subroutine, multiplicative weight updates compute a fractional solution combining cycle bases with low maximum congestion.The section reports a deterministic polynomial-time algorithm for this step.Source: §4 · p. 5, §4.2 · p. 6
4.1 Cycle Bases with Low Average Congestion
- Rizzi’s deterministic algorithm targets low weighted-average congestion, iteratively finding a simple cycle of length O(log n) and removing its heaviest edge.The algorithm runs in O(mn) time.Source: §4 · p. 5, §4.1 · p. 6
4 Algorithmic Sparse Cycle Basis
- A deterministic polynomial-time algorithm computes a cycle basis with O(log n) congestion, supplying the section’s main result.The result is Theorem 3.2.Source: §4.3 · p. 8
4.3 Deterministic Rounding: Proof of Theorem 3.2
- Deterministic swap rounding converts the fractional solution into one cycle basis while keeping the potential non-increasing, yielding O(log n) congestion.The argument starts with small potential and shows that a single basis with small potential has low congestion.Source: §4.3 · pp. 8–9
AI Disclosure
The authors report that ChatGPT 5.6 Sol was used in the proof’s initial discovery; they verified, simplified, and rewrote the proof, and assume responsibility for the paper’s content and correctness.
AI Disclosure
- The proof was initially discovered using ChatGPT 5.6 Sol.The authors say they verified, simplified, and rewrote it.Source: AI Disclosure · p. 10
- The authors state that they verified, simplified, and rewrote the proof.They assume responsibility for the paper’s content and correctness.Source: AI Disclosure · p. 10
- The authors assume responsibility for the paper’s content and correctness.Source: AI Disclosure · p. 10