Connectivity Labeling and Routing with Multiple Vertex Failures

We present succinct labeling schemes for answering connectivity queries in graphs subject to a specified number of vertex failures. An f -vertex/edge fault tolerant (f -V/EFT) connectivity labeling is a scheme that produces succinct labels for the vertices (and possibly to the edges) of an n-vertex graph G, such that given only the labels of two vertices s, t and of at most f faulty vertices/edges F , one can infer if s and t are connected in G -F . The primary complexity measure is the maximum label length (in bits).

The f -EFT setting is relatively well understood: [Dory and Parter, PODC 2021] gave a randomized scheme with succinct labels of O(log 3 n) bits, which was subsequently derandomized by [Izumi et al., PODC 2023] with Õ(f 2 )-bit labels. As both noted, handling vertex faults is more challenging. The known bounds for the f -VFT setting are far away: [Parter and Petruschka, DISC 2022] gave Õ(n 1-1/2 Θ(f ) )-bit labels, which is linear in n already for f = Ω(log log n).

In this work we present an efficient f -VFT connectivity labeling scheme using poly(f, log n) bits. Specifically, we present a randomized scheme with O(f 3 log 5 n)-bit labels, and a derandomized version with O(f 7 log 13 n)-bit labels, compared to an Ω(f )-bit lower bound on the required label length. Our schemes are based on a new low-degree graph decomposition that improves on [Duan and Pettie, SODA 2017], and facilitates its distributed representation into labels. This is accompanied with specialized linear graph sketches that extend the techniques of the Dory and Parter to the vertex fault setting, which are derandomized by adapting the approach of Izumi et al. and combining it with hit-miss hash families of [Karthik and Parter, SODA 2021].

Finally, we show that our labels naturally yield routing schemes avoiding a given set of at most f vertex failures with table and header sizes of only poly(f, log n) bits. This improves significantly over the linear size bounds implied by the EFT routing scheme of Dory and Parter.