Connectivity Labeling Schemes for Edge and Vertex Faults via Expander Hierarchies

We consider the problem of assigning short labels to the vertices and edges of a graph G so that given any query ⟨s, t, F ⟩ with |F | ≤ f , we can determine whether s and t are still connected in G -F , given only the labels of F ∪ s, t.

This problem has been considered when F ⊂ E (edge faults), where correctness is guaranteed with high probability (w.h.p.) [DP21] or deterministically [IEWM23], and when F ⊂ V (vertex faults), both w.h.p. and deterministically [PP22, PPP24]. Our main results are as follows. Deterministic Edge Faults. We give a new deterministic labeling scheme for edge faults that uses Õ( √ f )-bit labels, which can be constructed in polynomial time. This improves on Dory and Parter's [DP21] existential bound of O(f log n) (requiring exponential time to compute) and the efficient Õ(f 2 )-bit scheme of Izumi, Emek, Wadayama, and Masuzawa [IEWM23]. Our construction uses an improved edge-expander hierarchy and a distributed coding technique based on Reed-Solomon codes. Deterministic Vertex Faults. We improve Parter, Petruschka, and Pettie's [PPP24] deterministic O(f 7 log 13 n)-bit labeling scheme for vertex faults to O(f 4 log 7.5 n) bits, using an improved vertex-expander hierarchy and better sparsification of shortcut graphs. We completely bypass deterministic graph sketching [IEWM23] and hit-and-miss families [KP21]. Randomized Edge/Verex Faults. We improve the size of Dory and Parter's [DP21] randomized edge fault labeling scheme from O(minf + log n, log 3 n) bits to O(minf + log n, log 2 n log f ) bits, shaving a log n/ log f factor. We also improve the size of Parter, Petruschka, and Pettie's [PPP24] randomized vertex fault labeling scheme from O(f 3 log 5 n) bits to O(f 2 log 6 n) bits, which comes closer to their Ω(f )-bit lower bound [PPP24].