  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 \geq 2$ for any $n$-vertex graph. Our key result is $2$-VFT
connectivity labels with $O(\log^3 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(\log\log n)$, that are based on a reduction to the existing EFT
labels.
