Improved graph labeling technique quickly checks connectivity after edge failures
Deterministic Edge-Fault-Tolerant Connectivity Labeling Schemes with Nearly Optimal Label Size
Data Structures and Algorithms
Summary
When roads or connections in a network break, it becomes tricky to quickly tell if two places are still connected without checking everything again. This paper presents a way to give each point in the network a short 'label' so you can figure out if two points stay linked even if some connections fail, just by looking at these labels. The authors created a method that uses shorter labels than before, works reliably, and can be done with a step-by-step process rather than relying on guesswork. This helps in networks where a certain number of failures might happen, speeding up the connectivity checks significantly.
undirected graphconnectivityedge faultslabeling schemedeterministic algorithmpolynomial timecycle spacecycle basisfault tolerance
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.