# ~Optimal Dual Vertex Failure Connectivity Labels

arXiv: https://arxiv.org/abs/2208.10168 · HTML: https://mlsanity.com/paper/2208.10168/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Aug 2022.

## Built on by (most cited first, 1 of 1)

- [Connectivity Oracles for Predictable Vertex Failures](https://mlsanity.com/paper/2312.08489/) (2023)

## Abstract (arXiv)

In this paper we present succinct labeling schemes for supporting connectivity queries under vertex faults. For a given n-vertex graph G, an f-VFT (resp., EFT) connectivity labeling scheme is a distributed data structure that assigns each of the graph edges and vertices a short label, such that given the labels of a vertex pair u and v, and the labels of at most f failing vertices (resp., edges) F, one can determine if u and v are connected in G setminus F. The primary complexity measure is the length of the individual labels. Since their introduction by [Courcelle, Twigg, STACS '07], FT labeling schemes have been devised only for a limited collection of graph families. A recent work [Dory and Parter, PODC 2021] provided EFT labeling schemes for general graphs under edge failures, leaving the vertex failure case fairly open. We provide the first sublinear f-VFT labeling schemes for f ≥ 2 for any n-vertex graph. Our key result is 2-VFT connectivity labels with O(log3 n) bits. Our constructions are based on analyzing the structure of dual failure replacement paths on top of the well-known heavy-light tree decomposition technique of [Sleator and Tarjan, STOC 1981]. We also provide f-VFT labels with sub-linear length (in |V|) for any f=o(loglog n), that are based on a reduction to the existing EFT labels.