  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
$\tilde{O}(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 $\tilde{O}(n^{1-1/2^{\Theta(f)}})$-bit labels,
which is linear in $n$ already for $f =\Omega(\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 $\Omega(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. 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.
