Deterministic labeling improves fault-tolerant connectivity checks in networks
Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size
Data Structures and Algorithms
Summary
Finding out if two points in a network stay connected after some connections fail can be tricky. The authors show a way to give each point and connection a short label so you can quickly tell if two points remain connected after some failures. Their method is both efficient and guaranteed to work for all possible failures up to a given size. This improves on earlier methods by making the labels smaller and by giving stronger guarantees without randomness.
What this means in practice
- •For network engineers: Store concise labels on network devices to quickly check connectivity under link failures without global topology queries.
- •For distributed systems developers: Use compact deterministic labels to efficiently verify connectivity amid communication link faults during distributed computations.
Authors
Yaowei Long, Seth Pettie, Thatchaphol Saranurak
Abstract
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 = Ω(\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.