# Õptimal Dual Vertex Failure Connectivity Labels

Merav Parter
Weizmann Institute
<EMAIL_ADDRESS>This project is funded by the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (grant agreement No. 949083), and by the Israeli Science Foundation
(ISF), grant No. 2084/18. Asaf Petruschka
Weizmann Institute
<EMAIL_ADDRESS>
###### Abstract

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.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contribution
    2. 1.2 Preliminaries
  2. 2 Single Failure Connectivity Labels
  3. 3 Dual Failure Connectivity Labels
    1. 3.1 Technical Overview
    2. 3.2 Two Failures are Independent
    3. 3.3 Two Failures are Dependent
      1. 3.3.1 The All-Heavy (AH) Case
      2. 3.3.2 The General Dependent-Failures Case
  4. 4 Sublinear $f$-VFT Labels
  5. A Preprocessing Times
  6. B Distributed Computation of Labels and Cut Vertices
    1. B.1 Graph Sketches
    2. B.2 The Distributed Algorithms
  7. C Single-Source Dual Failure Connectivity Labels
    1. C.1 The Down Case: $y\in T_{x^{\prime}}$
    2. C.2 The Up Case: $y\in T[s,x)$
    3. C.3 The Side Case: $y\in T_{x}\setminus T_{x^{\prime}}$
    4. C.4 The Independent Case: $x$ and $y$ are Independent

##  1 Introduction

Connectivity labels are among the most fundamental distributed data-
structures, with a wide range of applications to graph algorithms, distributed
computing and communication networks. The error-prone nature of modern day
communication networks poses a demand to support a variety of logical
structures and services, in the presence of vertex and edge failures. In this
paper we study fault-tolerant (FT) connectivity labeling schemes, also known
in the literature as _forbidden-set_ labeling. In this setting, it is required
to assign each of the graph’s vertices (and possibly also edges) a short name
(denoted as _label_), such that given the labels of a vertex pair $u$ and $v$,
and the labels of a faulty-set $F$, it possible to deduce – using no other
information – whether $u$ and $v$ are connected in $G\setminus F$. Since their
introduction by Courcelle and Twigg [CT07] and despite much activity revolving
these topics, up until recently FT-labels have been devised only for a
restricted collection of graph families. This includes graphs with bounded
tree-width, planar graphs, and graphs with bounded doubling dimension [CT07,
ACG12, ACGP16]. Hereafter, FT-labeling schemes under $f$ faults of vertices
(resp., edge) are denoted by $f$-VFT labeling (resp., $f$-EFT).

A recent work by Dory and Parter [DP21] provided the first EFT-labeling
schemes for general $n$-vertex graphs, achieving poly-logarithmic label
length, independent of the number of faults $f$. For graphs with maximum
degree $\Delta$, their labels immediately provide VFT-labels with
$\widetilde{O}(\Delta)$ bits111By including in the label of vertex $v$ the EFT
labels of all edges incident to $v$.. The dependency on $\Delta$ is clearly
undesirable, as it might be linear in $n$. This dependency can be explained by
the fact that a removal of single vertex might decompose the graph into
$\Theta(\Delta)$ disconnected components. The latter behavior poses a
challenge for the labeling algorithm that must somehow compress the
information on this large number of components into a short label.

While the $\Delta$ dependency seems to be inherent in the context of
distributed vertex connectivity [PT11, Par19], Baswana and Khanna and Baswana
et al. [KB10, BCHR18] overcome this barrier for the single vertex fault case.
Specifically, they presented a construction of distance oracles and labels,
that maintain approximate distances in the presence of a single vertex fault
with near linear space. This provides, in particular, $1$-VFT approximate-
distance labels of polylogarithmic length. Their constructions are based on
exploiting the convenient structure of single-fault replacement paths. $1$-VFT
connectivity labels of logarithmic length are easy to achieve using block-cut
trees [Wes00], as discussed later on.

When turning to handling dual vertex failures, it has been noted widely that
there is a sharp qualitative difference between a single failure and two or
more failures. This one-to-two jump has been established by now for a wide-
variety of fault-tolerant settings, e.g., reachability oracles [Cho16],
distance oracles [DP09], distance preservers [Par15, GK17, Par20] and vertex-
cuts [HT73, BT89, BT96, GILP15]. In the lack of any $f$-VFT labeling scheme
with sublinear length for any $f\geq 2$, we focus on the following natural
question:

> _Is it possible to design dual vertex failure connectivity labels of
> $\widetilde{O}(1)$ length?_

The only prior $2$-VFT labeling schemes known in the literature have been
provided for _directed_ graphs in the special case of _single-source_
reachabilty by Choudhary [Cho16]. By using the well-known tool of independent
trees [GT12], [Cho16] presented a construction of dual-failure _single-source_
reachability data structures, that also provide labels of $O(\log^{3}n)$ bits.
Note that in a sharp contrast to undirected connectivity that admit $O(\log
n)$-bit labels, (all-pairs) reachability labels require _linear_ length, even
in the fault-free setting [DGJ20].

##### Representation of Small Vertex Cuts: Block-Cut and SPQR Trees.

The block-cut tree representation of a graph compactly encodes all of its
single cut vertices (a.k.a. articulation points), and the remaining connected
components upon the failure of each such vertex [Wes00]. By associating each
vertex of the original graph with a corresponding node in the block-cut tree
and using standard tree labels techniques, $1$-VFT connectivity labels are
easily achieved.

Moving on to dual failures, we have the similar (but more complex) SPQR-tree
representation [BT89], which encodes all cut pairs (i.e., vertex pair whose
joint failure disconnects the graph). However, it is currently unclear to us
how to utilize this structure for $2$-VFT connectivity labels. The main issue
is generalizing the vertex-node association from the block-cut tree to SPQR
tree: each vertex may appear in many nodes with different ‘virtual edges’
adjacent to it, corresponding to different cut-mates forming a cut-pair with
it.

Kanevsky, Tamassia, Di Battista, and Chen [KTBC91] extended the SPQR structure
to represent 3-vertex cuts. While these representations are currently limited
to cuts of size at most $3$, we hope that the approach taken in this paper can
be extended to handle larger number of faults. In addition, it is arguably
more distributed friendly, as it is based on basic primitives such as the
heavy-light tree decomposition, which can be easily implemented in the
distributed setting.

##### On the Gap Between Edge vs. Vertex Connectivity.

Recent years have witnessed an enormous progress in our understanding of
vertex cuts, from a pure graph theoretic perspective [PY21] to many
algorithmic applications [NSY19, LNP+21, PY21, HLW21]. Despite this exciting
movement, our algorithmic toolkit for handling vertex cuts is still
considerably limited compared to the counterpart setting of edge connectivity.
Indeed, near-linear time sequential algorithms for edge connectivity and
minimum weighted edge cuts are known for years since the celebrated result of
Karger [Kar93], and its recent improvements by [GNT20, GMW20]. In contrast,
only very recently, Forster et al. [FNY+20] provided the first near linear
time sequential algorithm for detecting small _vertex_ cuts of size
$\widetilde{O}(1)$. Despite a large collection of recent groundbreaking
results [NSY19, LNP+21, PY21, HLW21], to this date, no subquadratic-time
algorithm is known for the entire connectivity regime.

##### Additional Related Work.

Our dual-failure vertex connectivity labels are also closely related to
_connectivity sensitivity oracles_ [DP17, DP20], that provide low-space
centralized data-structure for supporting connectivity queries in presence of
vertex faults. The main goal in our setting is to provide a _distributed_
variant of such construction, where each vertex holds only $S(n)/n$ bits of
information, where $S(n)$ is the global space of the centralized data-
structure. Duan and Pettie [DP17, DP20] provided an ingenues construction that
supports multiple vertex faults in nearly optimal space of $\widetilde{O}(n)$.
These constructions are built upon highly centralized building blocks, and
their distributed implementation is fairly open.

###  1.1 Our Contribution

We first present new constructions of $1$-VFT and $2$-VFT labeling schemes
with polylogarithmic length. On a high level, our approach is based on
analyzing the structure of dual failure replacement paths, and more
specifically their intersection with a given heavy-light tree decomposition of
(a spanning tree of) the graph. Throughout, we denote the number of graph
vertices (edges) by $n$ (resp., $m$).

##### Warm-Up: $1$-VFT Connectivity Labels.

As a warm-up to our approach, we consider the single fault setting and provide
a simple label description that uses only the heavy-light decomposition
technique.

######  Theorem 1.1 ($1$-VFT Connectivity Labels).

For any $n$-vertex graph, there is a _deterministic_ $1$-VFT connectivity
labeling scheme with label length of $O(\log^{2}n)$ bits. The decoding
algorithm takes ${\rm poly}(\log n)$ time. The labels are computed in
$\widetilde{O}(m)$ randomized centralized time, or $\widetilde{O}(D)$
randomized congest rounds.

While this construction is presented mainly to introduce our technique, it
also admits an efficient distributed implementation which follows by the
recent work of [PP22].

#####  $2$-VFT Connectivity Labels.

We then turn to consider the considerably more involved setting of supporting
two vertex failures. In the literature, heavy-light tree decomposition have
been proven useful mainly for handling single vertex faults, e.g. in [KB10].
The only dual-failure scheme of [Cho16] is tailored to the _single-source_
setting. By carefully analyzing dual-failure replacement paths and their
interaction with the heavy-light tree decomposition of a given spanning tree,
we provide deterministic labeling schemes of $O(\log^{3}n)$ bits. Our main
technical contribution in this paper is stated as follow:

######  Theorem 1.2 ($2$-VFT Connectivity Labels).

For any $n$-vertex graph, there is a deterministic $2$-VFT connectivity
labeling scheme with label length of $O(\log^{3}n)$ bits. The decoding
algorithm takes ${\rm poly}(\log n)$ time. The labels are computed in
$\widetilde{O}(n^{2})$ time.

Our dual-failure labeling scheme uses, in a complete black-box manner, single-
source labels. For this purpose, we can use the $O(\log^{3}n)$-bit labels of
Choudhary [Cho16]. We also provide an alternative construction that is based
on the undirected tools of heavy-path tree decomposition, rather than using
the tool of independent trees as in [Cho16]. Our single-source labels provide
a somewhat improved length of $O(\log^{2}n)$ bits222We note that it might also
be plausible to improve the label size of [Cho16] to $O(\log^{2}n)$ bits, by
reducing the size of their range-minima labels., but more importantly convey
intuition for our all-pairs constructions. Since our labels are built upon a
single arbitrary spanning tree that can be assumed to have depth $O(D)$, we
are hopeful that this approach is also more distributed-friendly.
Specifically, as the depth of the independent trees using in [Cho16] might be
linear in $n$, their distributed computation might be too costly for the
purpose of dual vertex cut computation. Moreover, currently the tool of
independent trees is limited to only two cut vertices, which also poses a
barrier for extending this technique to handle multiple faults. In Appendix C,
we show:

######  Lemma 1.3.

There is a _single-source_ 2-VFT connectivity labeling scheme with label
length $O(\log^{2}n)$ bits. That is, given an $n$-vertex graph $G$ with a
fixed source vertex $s$, one can label the vertices of $G$ such that given
query of vertices $\langle t,x,y\rangle$ along with their labels, the
connectivity of $s$ and $t$ in $G\setminus\\{x,y\\}$ can be inferred.

#####  $f$-VFT Connectivity Labels.

Finally, we turn to consider labeling schemes in the presence of multiple
vertex faults. By combining the notions of sparse vertex certificates [CKT93]
with the EFT-labeling scheme of [DP21], in Appendix 4 we show:

######  Theorem 1.4 ($f$-VFT Connectivity Labels).

There is a $f$-VFT connectivity labeling scheme with label length
$\widetilde{O}(n^{1-1/2^{f-2}})$ bits, hence of sublinear length of any
$f=o(\log\log n)$.

This for example, provides $3$-VFT labels of $\widetilde{O}(\sqrt{n})$ bits.

###  1.2 Preliminaries

Given a connected $n$-vertex graph $G=(V,E)$, we fix an arbitrary source
vertex $s\in V$, and a spanning tree $T$ of $G$ rooted at $s$. We assume each
vertex $a$ is given a unique $O(\log n)$-bit identifier
$\operatorname{ID}(a)$. Let $par(a)$ be the parent of $a$ in $T$, $T_{a}$ be
the subtree of $T$ rooted at $a$, and $T_{a}^{+}$ be the tree obtained from
$T_{a}$ by connecting $par(a)$ to $a$. The (unique) tree path between two
vertices $a,b$ is denoted $T[a,b]$.333Note that $T[a,b]$ is a path, but
$T_{a}$ is a subtree. Let $0pt(a)$ be the hop-distance of vertex $a$ from the
root $s$ in $T$, i.e. the number of edges $T[s,a]$. We say that vertex $a$ is
_above_ or _higher_ (resp., _below_ or _lower_) than vertex $b$ if $0pt(a)$ is
smaller (resp., larger) than $0pt(b)$. The vertices $a,b$ are said to be
_dependent_ if $a$ is an ancestor of $b$ in $T$ or vice-versa, and
_independent_ otherwise. We denote by $\operatorname{LCA}(A)$ the lowest/least
common ancestor in $T$ of all vertices in $A\subseteq V$.

For two paths $P,Q\subseteq G$, define the concatenation $P\circ Q$ as the
path formed by concatenating $Q$ to the end of $P$. The concatenation is well
defined if for the last vertex $p_{\ell}$ of $P$ and the first vertex $q_{f}$
of $Q$ it either holds that $p_{\ell}=q_{f}$ or that $(p_{\ell},q_{f})\in E$.
We use the notation $P(a,b]$ for the subpath of $P$ between vertices $a$ and
$b$, excluding $a$ and including $b$. The subpaths $P[a,b)$, $P[a,b]$ and
$P(a,b)$ are defined analogously. We extend this notation for tree paths, e.g.
$T(a,b]$ denotes the subpath of $T[a,b]$ obtained by omitting $a$. When we
specify $P$ as an $a$-$b$ path, we usually think of $P$ as directed from $a$
to $b$. E.g., a vertex $c\in P$ is said to be the _first_ having a certain
property if it is the closest vertex to $a$ among all vertices of $P$ with the
property. A path $P$ _avoids_ a subgraph $H\subseteq G$ if they are vertex
disjoint, i.e. $V(P)\cap V(H)=\emptyset$.

For a subgraph $G^{\prime}\subseteq G$, let $\deg(a,G^{\prime})$ be the degree
of vertex $a$ in $G^{\prime}$. We denote by $\mathsf{conn}(a,b,G^{\prime})$
the connectivity status of vertices $a$ and $b$ in $G^{\prime}$, which is $1$
if $a$ and $b$ are connected in $G^{\prime}$ and $0$ otherwise. We give
arbitrary unique $O(\log n)$-bit IDs to the connected components of
$G^{\prime}$, e.g. by taking the maximal vertex ID in each component. We
denote by $\mathsf{CID}(a,G^{\prime})$ the ID of the connected component
containing vertex $a$ in $G^{\prime}$. For a failure (or fault) set
$F\subseteq V$, we say that two vertices $a,b$ are _$F$ -connected_ if
$\mathsf{conn}(a,b,G\setminus F)=1$, and _$F$ -disconnected_ otherwise. In the
special cases where $F=\\{x\\}$ or $F=\\{x,y\\}$ for some $x,y\in V$, we use
respectively the terms $x$-connected or $xy$-connected.

##### Replacement Paths.

For a given (possibly weighted) graph $G$, vertices $a,b\in V$ and a faulty
set $F\subseteq V$, the _replacement path_ $P_{a,b,F}$ is the shortest $a$-$b$
path in $G\setminus F$. In our context, as we are concerned with connectivity
rather than in shortest-path distances, we assign weights to the graph edges
for the purpose of computing replacement paths with some convenient structure
w.r.t a given spanning tree $T$. Specifically, by assigning weight of $1$ to
the $T$-edges, and weight $n$ to non $T$-edges, the resulting replacement
paths “walk on $T$ whenever possible”. Formally, this choice of weights
ensures the following property of the replacement paths: for any two vertices
$c,d\in P_{a,b,F}$ such that $T[c,d]\cap F=\emptyset$,
$P_{a,b,F}[c,d]=T[c,d]$. Also note that these replacement paths are shortest
w.r.t our weight assignment, but might not be shortest w.r.t their number of
edges. We may write $P_{a,b,x}$ when $F=\\{x\\}$.

##### Heavy-Light Tree Decomposition.

Our labeling schemes use the classic heavy-light tree decomposition technique
introduced by Sleator and Tarjan [ST83]. This is inspired by the work of
Baswana and Khanna [KB10] applying this technique in the fault-tolerant
setting. The _heavy child_ of a non-leaf vertex $a$ in $T$, denoted $h(a)$, is
the child $b$ of $a$ that maximizes the number of vertices in its subtree
$T_{b}$ (ties are broken arbitrarily in a consistent manner.). A vertex is
called _heavy_ if it is the heavy child of its parent, and _light_ otherwise.
A tree edge in $T$ is called _heavy_ if it connects a vertex to its heavy
child, and _light_ otherwise. The set of heavy edges induces a collection of
tree paths, which we call _heavy paths_. Let $a,b\in V$ such that $a$ is a
strict ancestor of $b$, and let $a^{\prime}$ be the child of $a$ on $T[a,b]$.
Then $a$ is called a _heavy ancestor_ of $b$ if $a^{\prime}$ is heavy, or a
_light ancestor_ of $b$ if $a^{\prime}$ is light. Note that a heavy ancestor
of $b$ need not be a heavy vertex itself, and similarly for light ancestors.
We observe that if $b$ is a light child of $a$, then $T_{b}$ contains at most
half of the vertices in $T_{a}$. Consequently, we have:

######  Observation 1.1.

Any root-to-leaf path in $T$ contains only $O(\log n)$ light vertices and
edges.

Our labeling schemes are based on identifying for each vertex $a$ a small
number of interesting vertices, selected based on the heavy-light
decomposition.

######  Definition 1.1.

The _interesting set_ of a vertex $a$ is defined to be $I(a)=\\{b\in
T[s,a]\mid b\text{ is light}\\}\cup\\{h(a)\\}$ (where $\\{h(a)\\}$ is
interpreted as the empty set if $a$ is a leaf). That is, $I(a)$ consists of
all the light vertices on $T[s,a]$, along with the heavy child of $a$ (if it
exists). The _upper-interesting set_ of $a$ is defined to be
$I^{\uparrow}(a)=\\{par(b)\mid b\in I(a)\\}\cup\\{a\\}$. That is,
$I^{\uparrow}(a)$ consists of all the light ancestors of $a$ and $a$ itself.

We make extensive use of the following useful properties of interesting sets,
which are immediate to prove.

######  Lemma 1.5.

For any $a\ \in V$, $|I(a)|=O(\log n)$ and $|I^{\uparrow}(a)|=O(\log n)$.

######  Lemma 1.6.

Let $a,b\in V$ such that $a\in T[s,b]$.

(1) If $a\neq b$, then for the child $a^{\prime}$ of $a$ on $T[a,b]$ it holds
that $a^{\prime}\in I(a)\cup I(b)$.

(2) If $a\notin I^{\uparrow}(b)$, then $a\neq b$ and the child of $a$ on
$T[a,b]$ is $h(a)$.

##### Extended Vertex IDs.

To avoid cumbersome definitions in our labels, it is convenient to augment the
vertex IDs with additional $O(\log n)$ bits of information, resulting in
_extended IDs_. The main ingredient is _ancestry labels_ [KNR92]: these are
$O(\log n)$-bit labels $\mathsf{ANC}_{T}(a)$ for each vertex $a$, such that
given $\mathsf{ANC}_{T}(a)$ and $\mathsf{ANC}_{T}(b)$ one can infer whether
$a$ is an ancestor of $b$ in $T$. The extended ID of a vertex $a$ is444If $a$
is a leaf, we simply omit from $\operatorname{EID}(a)$ the information
regarding $h(a)$.
$\operatorname{EID}(a)=\left[\operatorname{ID}(a),\mathsf{ANC}_{T}(a),\operatorname{ID}(h(a)),\mathsf{ANC}_{T}(h(a))\right]$.
Thus, given $\operatorname{EID}(a)$ and $\operatorname{EID}(b)$, one can
determine whether $a$ is an ancestor of $b$ in $T$, and moreover, whether it
is a light or a heavy ancestor. We will not explicitly refer to the extended
IDs, but rather use them as follows:

  * •

The label of any vertex $a$ always (implicitly) stores
$\operatorname{EID}(a)$.

  * •

Whenever a label stores a given vertex $a$, it additionally stores
$\operatorname{EID}(a)$.

This enables us to assume throughout that we can always determine the (heavy
or light) ancestry relations of the vertices at play.

##  2 Single Failure Connectivity Labels

In this section we warm-up by considering the single failure case of Theorem
1.1.

1 for  _each $b^{\prime}\in I(a)$ with $par(b^{\prime})=b$_ do

2 store vertices $b,b^{\prime}$ and the values
$\mathsf{conn}(s,b^{\prime},G\setminus\\{{b}\\})$,
$\mathsf{CID}(b^{\prime},G\setminus\\{{b}\\})$;

3

Algorithm 1 Construction of label $\mathsf{L}_{\mathsf{{1F}}}(a)$ for vertex
$a$

The key observation for decoding is:

######  Claim 2.1.

Given $\mathsf{L}_{\mathsf{{1F}}}(w)$ and $\mathsf{L}_{\mathsf{{1F}}}(x)$, one
can determine the $x$-connectivity of $w$ and $s$, and also find
$\mathsf{CID}(w,G\setminus\\{{x}\\})$ in case $w,s$ are $x$-disconnected.

###### Proof.

If $w$ is not a descendant555This is checked using extended IDs
$\operatorname{EID}(w)$ and $\operatorname{EID}(x)$. of $x$, then $T[s,w]$ is
failure-free, so $w$ and $s$ are $x$-connected and we are done. Assume now
that $w$ is a descendant of $x$, and let $x^{\prime}$ be the child of $x$ on
$T[x,w]$. Then $T[x^{\prime},w]$ is failure-free, hence $x^{\prime}$ and $w$
are $x$-connected. Therefore, it suffices to determine the values
$\mathsf{conn}(s,x^{\prime},G\setminus\\{{x}\\})$ and
$\mathsf{CID}(x^{\prime},G\setminus\\{{x}\\})$. Lemma 1.6(1) guarantees that
$x^{\prime}\in I(w)\cup I(x)$, hence the required values are stored either in
$\mathsf{L}_{\mathsf{{1F}}}(w)$ or in $\mathsf{L}_{\mathsf{{1F}}}(x)$ (by
setting $b=x$ and $b^{\prime}=x^{\prime}$). ∎

Given $\mathsf{L}_{\mathsf{{1F}}}(u)$, $\mathsf{L}_{\mathsf{{1F}}}(v)$ and
$\mathsf{L}_{\mathsf{{1F}}}(x)$, we determine the $x$-connectivity of $u,v$ as
follows. We apply Claim 2.1 twice, with $w=u$ and with $w=v$. If we find the
component IDs of both $u$ and $v$ in $G\setminus\\{{x}\\}$, we compare them
and answer accordingly. However, if this is not the case, then we must
discover that one of $u,v$ is $x$-connected to $s$, so we should answer
affirmatively iff the other is $x$-connected to $s$. This completes the
decoding algorithm of Theorem 1.1. The preprocessing time analysis is deferred
Appendix A.

##  3 Dual Failure Connectivity Labels

###  3.1 Technical Overview

In the following we provide high-level intuition for our main technical
contribution of dual failure connectivity labels. Throughout, the query is
given by the tuple $\langle u,v,x,y\rangle$, where $x,y$ are the vertex
faults. Recall that our construction is based on some underlying spanning tree
$T$ rooted at some vertex $s$ (that we treat as the _source_). Similarly to
the $1$-VFT construction, we compute the heavy-light tree decomposition of
$T$, which classifies the tree edges into heavy and light.

We distinguish between two structural cases depending on the locations of the
two faults, $x$ and $y$. The first case which we call _dependent_ handles the
setting where $x$ and $y$ have ancestry/descendant relations. The second
_independent_ case assumes that $x$ and $y$ are not dependent, i.e.,
$\operatorname{LCA}(x,y)\notin\\{x,y\\}$.

Our starting observation is that by using single-source $2$-VFT labels in a
black-box manner, we may restrict our attention to the hard case where the
source $s$ is $xy$-disconnected from both $u$ and $v$. Quite surprisingly,
this assumption yields meaningful restrictions on the structure of key
configurations, as will be demonstrated shortly.

##### Dependent Failures.

To gain intuition, we delve into two extremes: the easy _all-light_ case where
$u,v,y$ are all _light_ descendants of $x$, and the difficult _all-heavy_ case
where they are all _heavy_ descendants of $x$. Consider first the easy all-
light case. As every vertex has only $O(\log n)$ light ancestors, each of
$u,v,y$ has the budget to prepare by storing its $1$-VFT label w.r.t the graph
$G\setminus\\{{x}\\}$. Then, for decoding, we simply answer the single-failure
query $\langle u,v,y\rangle$ in $G\setminus\\{{x}\\}$.

We turn to consider the all-heavy case, which turns out to be an important
core configuration. Here, we no longer have the budget to prepare for each
possible failing $x$, and a more careful inspection is required. The
interesting case is when $y\in T[u,v]$. We further focus in this overview on
the following instructive situation: $y$ is not an ancestor of $v$, but is a
_heavy_ ancestor of $u$. It is then sufficient to determine the
$xy$-connectivity of $h(y)$ and $par(y)$. See Figure 1 (left).

[scale=0.5]fig_tech_overview.pdf

Figure 1:  Left: Illustration of the all-heavy configuration. Letting
$P=P_{h(y),par(y),y}$, the purple path represents the prefix $P[h(y),f]$ of
$P$ until the first time it hits $T[s,par(y)]$. Vertices $f_{1},f_{2},f_{3}$
correspond to different options for the location of $f$: above $x$, equals
$x$, or below $x$. The $f_{1}$ option is marked X as it is excluded by our
analysis. Right: Illustration of the reduction to the all-heavy case. The
analog vertices $\widehat{u},\widehat{v}$ are chosen from
$\mathsf{AnSet}(u,x),\mathsf{AnSet}(v,x)$, respectively.

Naturally, $y$ is most suited to prepare in advance for this situation, as
follows. Let $P=P_{h(y),par(y),y}$ be the $h(y)$-$par(y)$ replacement path
avoiding $y$, and let $f\in P$ be the _first_ vertex (i.e., closest to $h(y)$)
from $T[s,par(y)]$. Surprisingly, it suffices for the labeling algorithm to
include in the label of $y$ the identity of $f$, along with a single bit
representing the connectivity of $h(y)$ and $par(y)$ in $G\setminus\\{f,y\\}$.

This limited amount of information turns out to be sufficient thanks to the
useful structures of the replacement paths. Since $x$ is an ancestor of $y$,
we need to consider the possible locations of $x$ within $T[s,par(y)]$. The
key observation is that $x$ cannot lie below $f$, i.e. in $T(f,par(u)]$:
otherwise, $T[u,h(y)]\circ P[h(y),f]\circ T[f,s]$ is a $u$-$s$ path avoiding
$x,y$, which we assume does not exist! Now, if $x$ is above $f$, i.e. in
$T[s,f)$, then $P$ is fault-free, so we determine that $h(y),par(y)$ are
$xy$-connected. If $x=f$, we simply have the answer stored explicitly by the
label of $y$. The complete solution for the all-heavy case is of a similar
flavor, albeit somewhat more involved.

We then handle the general dependent failures case by reducing to the all-
heavy configuration, which we next describe in broad strokes. First, the case
where $y$ is a light descendant of $x$ is handled directly using $1$-VFT
labels, in a similar manner to the all-light case. In the remaining case where
$y\in T_{h(x)}$, a challenge arises when (at least) one of $u,v$, say $u$, is
a light descendant of $x$. We exploit the fact that the label of $u$ has the
_budget_ to prepare for light ancestors, and store in this label a small and
carefully chosen set of vertices from $T_{h(x)}$, called the _analog set_
$\mathsf{AnSet}(u,x)$. Our decoding algorithm in this case replaces the given
$\langle u,v,x,y\rangle$ query with an _analogous_ all-heavy query
$\langle\widehat{u},\widehat{v},x,y\rangle$ for some
$\widehat{u}\in\mathsf{AnSet}(u,x)$ and $\widehat{v}\in\mathsf{AnSet}(v,x)$.
See Figure 1 (right). The reduction’s correctness is guaranteed by the
definition of analog sets.

##### Independent Failures.

Our intuition comes from our solution to the _single-source_ independent-
failures case, described in Appendix C.4. As we assume that both $u,v$ are
$xy$-disconnected from $s$, we know that the corresponding decoding algorithm
_rejects_ both queries $\langle u,x,y\rangle$ and $\langle v,x,y\rangle$.
Rejection instances can be of two types: _explicit reject_ or _implicit
reject_.

If $\langle u,x,y\rangle$ is an explicit reject instance, then the algorithm
rejects by tracking down an explicit bit stored in one of the labels of
$u,x,y$, and returning it. This bit is of the form
$\mathsf{conn}(s,\widetilde{u},G\setminus\\{{x,y}\\})$ for some vertex
$\widetilde{u}$ which is $xy$-connected to $u$. So, in explicit reject
instances, one of the vertices $u,x,y$ has _prepared in advance_ by storing
this bit. In contrast, if it is an implicit reject instance, then the
algorithm detects _at query time_ that $\langle u,x,y\rangle$ match a
specific, highly-structured fatal configuration leading to rejection.
Specifically, this configuration implies that $u$ is $xy$-connected to both
$h(x)$ and $h(y)$. Thus, when reaching implicit rejection, we can infer useful
structural information.

Getting back to our original query $\langle u,v,x,y\rangle$, the idea is to
handle all of the four possible combinations of implicit or explicit rejects
for $\langle u,x,y\rangle$ or $\langle v,x,y\rangle$. Our approach is then
based on augmenting the single-source $2$-VFT labels in order to provide the
decoding algorithm with a richer information in the explicit rejection cases.

The presented formal solution distills the relevant properties of the
corresponding (augmented) single-source labels and decoding algorithm. This
approach has the advantage of having a succinct, clear and stand-alone
presentation which does not require any prior knowledge of our single-source
solution, but might hide some of the aforementioned intuition.

##### Setting Up the Basic Assumptions.

We now precisely describe the basic assumptions that we enforce as preliminary
step. These are:

  1. (C1)

$u$ and $v$ are both $x$-connected and $y$-connected.

  2. (C2)

Both $u$ and $v$ are $xy$-disconnected from the source $s$.

To verify condition (C1), we augment the $2$-VFT label of each vertex with its
$1$-VFT label from Theorem 1.1. If (C1) is not satisfied, then clearly $u,v$
are $xy$-disconnected, so we are done. For (C2), we further augment the labels
with the corresponding single-source $2$-VFT labels of [Cho16] (or
alternatively, our own such labels of Lemma 1.3). Using them we check whether
$u$ and $v$ are $xy$-connected to $s$. If both answers are affirmative, then
$u,v$ are $xy$-connected. If the answers are different, then $u,v$ are
$xy$-disconnected. Hence, the only non-trivial situation is when (C2) holds.
As the $1$-VFT and single-source $2$-VFT labels consume only $O(\log^{3}n)$
bits each, the above mentioned augmentations are within our budget.

The following sections present our $2$-VFT connectivity labeling scheme in
detail: Section 3.2 handles the independent-failures case, and Section 3.3
considers the dependent-failure case. The final label is obtained by adding
the sublables provided in each of these sections. We note that by using the
extended IDs of the vertices, it is easy for the decoding algorithm to detect
which of the cases fits the given $\langle u,v,x,y\rangle$ query.

###  3.2 Two Failures are Independent

The independence of the failures allows us to enforce a stronger version of
condition (C1):

  1. (C3)

$u$, $v$ and $s$ are all $x$-connected and $y$-connected.

Condition (C3) is verified using the 1-VFT labels of $u,v,x,y$ and $s$. As the
label of $s$ is not given to us, we just augment the label of every vertex
also with the $1$-VFT label of $s$. If (C3) fails, we are done by the
following claim. Missing proofs are deferred to Appendix A.

######  Claim 3.1.

If condition (C3) does not hold, then $u$ and $v$ are $xy$-connected.

###### Proof.

Assume (C3) does not hold. By (C1), this can happen only if one of $u,v$, say
$u$, is disconnected from $s$ under one of the failures, say $x$. Namely,
$u,s$ are $x$-disconnected. Now, (C1) also ensures that there is a $u$-$v$
path $P$ avoiding $x$. We assert that $P$ also avoids $y$, which completes the
proof. Assume otherwise, and consider the $u$-$s$ path $P^{\prime}=P[u,y]\circ
T[y,s]$. By the independence of $x,y$ we have that $x\notin P^{\prime}$, which
contradicts the fact that $u,s$ are $x$-disconnected. ∎

Our general strategy is to design labels $\mathsf{L}_{\mathsf{{P}}}(a)$ for
each vertex $a$ that have following property:

  1. (P)

For any $\langle u,v,x,y\rangle$ with independent failures666Which satisfy
conditions (C1), (C2) and (C3). $x,y$, there exists777At least one of
$h(x),h(y)$ exists: else, $x,y$ are leaves, so $T\setminus\\{x,y\\}$ spans
$G\setminus\\{{x,y}\\}$, contradicting (C2). $z\in\\{h(x),h(y)\\}$ such that
given the label $\mathsf{L}_{\mathsf{{P}}}(w)$ of any $w\in\\{u,v\\}$ and the
labels $\mathsf{L}_{\mathsf{{P}}}(x),\mathsf{L}_{\mathsf{{P}}}(y)$, one can
infer the $xy$-connectivity of $w,z$, and also find
$\mathsf{CID}(w,G\setminus\\{{x,y}\\})$ in case $w,z$ are $xy$-disconnected.

This suffices to determine the $xy$-connectivity of $u,v$ by the following
lemma:

######  Lemma 3.2.

Given the $\mathsf{L}_{\mathsf{{P}}}$ labels of $u,v,x,y$, one can determine
the $xy$-connectivity of $u,v$.

###### Proof.

We apply property (P) twice, for $w=u$ and for $w=v$. If we find the component
IDs of both $u$ and $v$ in $G\setminus\\{{x,y}\\}$ we just compare them and
answer accordingly. However, if this does not happen, then we must discover
that one of $u,v$ is $xy$-connected to $z$, so we should answer affirmatively
iff the other is also $xy$-connected to $z$. ∎

In order to preserve the symmetry between the independent failures $x$ and $y$
(which we prefer to break in a more favorable manner in our subsequent
technical arguments), we do not explicitly specify, at this point, the
identity of $z\in\\{h(x),h(y)\\}$. It may be useful for the reader to think of
$z$ as chosen _adversarially_ from $\\{h(x),h(y)\\}$, and our decoding
algorithm handles each of the two possible selections. Alternatively, this can
be put as follows: our labeling scheme will guarantee property (P) for
$z=h(x)$ _and_ for $z=h(y)$ (if both heavy children exist).

##### Construction of $\mathsf{L}_{\mathsf{{P}}}$ Labels.

We start with a useful property of single-fault replacement paths. For a
vertex $a\in V$ with an $s$-$a$ replacement path $P=P_{s,a,par(a)}$, let
$\ell_{a}\in P$ be the last (closest to $a$) vertex in $T\setminus
T_{par(a)}$.

######  Observation 3.1.

$P_{s,a,par(a)}=T[s,\ell_{a}]\circ Q$ where $Q\subseteq T_{par(a)}$.

We are now ready to define the $\mathsf{L}_{\mathsf{{P}}}$ labels. These are
constructed by Algorithm 2. The label length of $O(\log^{3}n)$ bits follows by
Lemma 1.5.

1 for  _each $b^{\prime}\in I(a)$ with $par(b^{\prime})=b$_ do

2 store vertices $b,b^{\prime},\ell_{b^{\prime}}$;

3 for  _each $c\in I^{\uparrow}(\ell_{b^{\prime}})$_ do

4 store vertex $c$;

5 store $\mathsf{CID}(b^{\prime},G\setminus\\{{b,c}\\})$,
$\mathsf{conn}(b^{\prime},h(b),G\setminus\\{{b,c}\\})$,
$\mathsf{conn}(b^{\prime},h(c),G\setminus\\{{b,c}\\})$;

6

7

Algorithm 2 Construction of label $\mathsf{L}_{\mathsf{{P}}}(a)$ for vertex
$a$

##### Decoding Algorithm for Property (P)

Our goal is to show that given $\mathsf{L}_{\mathsf{{P}}}(w)$ for
$w\in\\{u,v\\}$ and
$\mathsf{L}_{\mathsf{{P}}}(x),\mathsf{L}_{\mathsf{{P}}}(y)$ we can indeed
satisfy the promise of (P); namely, determine the $xy$-connectivity of $w,z$,
and in case they are $xy$-disconnected also report
$\mathsf{CID}(w,G\setminus\\{{x,y}\\})$.

One of the failures, say $x$, must be an ancestor of $w$ in $T$. Otherwise,
$w$ would have been connected to $s$ in $G\setminus\\{{x,y}\\}$, contradicting
(C2). Denote by $x^{\prime}$ the child of $x$ on $T[x,w]$. The independence of
$x,y$ guarantees that $T[x^{\prime},w]$ is fault-free, hence $x^{\prime},w$
are $xy$-connected.

It now follows from (C2) that $x^{\prime},s$ are $xy$-disconnected, and from
(C3) that $x^{\prime},s$ are $x$-connected. The latter ensures that
$\ell_{x^{\prime}}$ is well-defined. By Observation 3.1,
$P_{s,x^{\prime},x}=T[s,\ell_{x^{\prime}}]\circ Q$ where $Q\subseteq T_{x}$,
so $y\notin Q$. On the other hand, it cannot be $P_{s,x^{\prime},x}$ entirely
avoids $y$, as we have already established that $s,x^{\prime}$ are
$xy$-disconnected. It follows that $y\in T[s,\ell_{x^{\prime}}]$. See
illustration in Figure 2.

[scale=0.5]fig_ind.pdf

Figure 2:  Illustration of the decoding algorithm for the independent failures
case. The path $T[s,\ell_{x^{\prime}}]$ is shown in green (right), and the
path $Q$ is shown in purple (left). The concatenation
$T[s,\ell_{x^{\prime}}]\circ Q$ forms the replacement path
$P_{s,x^{\prime},x}$. The vertex $y^{\prime}$ is the child of $y$ on
$T[s,\ell_{x^{\prime}}]$. The case where $y\notin
I^{\uparrow}(\ell_{x^{\prime}})$ corresponds to $y^{\prime}=h(y)$.

Note that $x^{\prime}\in I(w)\cup I(x)$ by Lemma 1.6, hence the triplet of
vertices $b=x$, $b^{\prime}=x^{\prime}$ and
$\ell_{b^{\prime}}=\ell_{x^{\prime}}$ is stored either in
$\mathsf{L}_{\mathsf{{P}}}(w)$ or in $\mathsf{L}_{\mathsf{{P}}}(x)$. We next
distinguish between two cases, depending on whether $y$ belongs to the upper-
interesting set of $\ell_{x^{\prime}}$.

Case 1: $y\in I^{\uparrow}(\ell_{x^{\prime}})$. Then the following are also
specified in the last label (with $c=y$):

$\mathsf{CID}(x^{\prime},G\setminus\\{{x,y}\\}),\;\mathsf{conn}(x^{\prime},h(x),G\setminus\\{{x,y}\\}),\;\mathsf{conn}(x^{\prime},h(y),G\setminus\\{{x,y}\\}).$

Since $x^{\prime},w$ are $xy$-connected, we can replace $x^{\prime}$ by $w$ in
the three values above, and reporting them guarantees property (P).

Case 2: $y\notin I^{\uparrow}(\ell_{x^{\prime}})$. Then the child of $y$ on
$T[y,\ell_{x^{\prime}}]$ is $h(y)$ by Lemma 1.6. Thus
$T[h(y),\ell_{x^{\prime}}]\circ Q$ is a $h(y)$-$x^{\prime}$ path avoiding both
$x$ and $y$. Therefore, as $w$ is $xy$-connected to $x^{\prime}$, it is also
$xy$-connected to $h(y)$. So, if $z=h(y)$ we are done. However, if $z=h(x)$,
we recover by simply repeating the algorithm when $y,h(y),x$ play the
respective roles of $x,x^{\prime},y$. The triplet $y,h(y),\ell_{h(y)}$ is
stored $\mathsf{L}_{\mathsf{{P}}}(y)$ since $h(y)\in I(y)$. If $x\in
I^{\uparrow}(\ell_{h(y)})$, this label also specifies

$\mathsf{CID}(h(y),G\setminus\\{{x,y}\\}),\;\mathsf{conn}(h(y),h(x),G\setminus\\{{x,y}\\}),\;$

and since $w,h(y)$ are $xy$-connected we can replace $h(y)$ by $w$ in these
values, and report them to guarantee property (P). Otherwise, we deduce (by a
symmetric argument) that $w$ and $h(x)=z$ are $xy$-connected, so we are done.
This concludes the decoding algorithm for property (P). Finally, by Lemma 3.2,
we obtain:

######  Lemma 3.3.

There are $O(\log^{3}n)$-bit labels $\mathsf{L}_{\mathsf{{ind}}}$ supporting
the independent failures case.

###  3.3 Two Failures are Dependent

In this section, we consider the complementary case where $x$ and $y$ are
dependent. As previously discussed, our strategy is based on reducing the
general dependent-failures case to the well-structured configuration of the
all-heavy case:

######  Definition 3.1.

A query of vertices $\langle u,v,x,y\rangle$ is said to be _all-heavy (AH)_ if
$u,v,y\in T_{h(x)}$.

We first handle this configuration in Section 3.3.1 by defining sub-labels
$\mathsf{L}_{\mathsf{{AH}}}$ that are tailored to handle it. Then, Section
3.3.2 considers the general dependent-failures case.

####  3.3.1 The All-Heavy (AH) Case

##### Construction of $\mathsf{L}_{\mathsf{{AH}}}$ Labels.

We observe another useful property of single-fault replacement paths. For a
vertex $a\in V$ with an $a$-$s$ replacement path $P=P_{a,s,par(a)}$, let
$f_{a}\in P$ be the first (closest to $a$) vertex in $T[s,par(a))$.

######  Observation 3.2.

$P_{a,s,par(a)}=Q\circ T[f_{a},s]$ where $Q$ avoids $T[s,par(a)]$.

We are now ready to define the $\mathsf{L}_{\mathsf{{AH}}}$ labels. These are
constructed by Algorithm 3. The label length of $O(\log^{2}n)$ bits follows by
Lemma 1.5.

1 for  _each $b^{\prime}\in I(a)$ with $par(b^{\prime})=b$_ do

2 store vertices $b,b^{\prime},f_{b^{\prime}}$;

3 store $\mathsf{conn}(b^{\prime},par(b),G\setminus\\{{b,f_{b^{\prime}}}\\})$,
$\mathsf{CID}(b^{\prime},G\setminus T[s,b])$;

4

Algorithm 3 Construction of label $\mathsf{L}_{\mathsf{{AH}}}(a)$ for vertex
$a$

##### Decoding Algorithm for (AH) Case.

Assume we are given an (AH)-query $\langle u,v,x,y\rangle$ along with the
$\mathsf{L}_{\mathsf{{AH}}}$ labels of these vertices. The main idea behind
the construction of the $\mathsf{L}_{\mathsf{{AH}}}$ labels is to have:

######  Claim 3.4.

If $w\in\\{u,v\\}$ is a descendant of $y$, then given the
$\mathsf{L}_{\mathsf{{AH}}}$ labels of $w,x,y$, one can:

(1) find $\mathsf{CID}(w,G\setminus T[s,y])$, and

(2) determine whether $w$ and $par(y)$ are $xy$-connected.

###### Proof.

Let $y^{\prime}$ be the child of $y$ on $T[y,w]$. Then $y^{\prime},w$ are
$xy$-connected as $T[y^{\prime},w]$ is fault-free. Hence, in the following we
can replace $w$ by $y^{\prime}$ for determining both (1) and (2). Also, as
$w,y^{\prime}$ are (particularly) $y$-connected, and $w,s$ are $y$-connected
by (C1), we have that $y^{\prime},s$ are $y$-connected, so $f_{y^{\prime}}$ is
well-defined. By Lemma 1.6, it holds that $y^{\prime}\in I(w)\cup I(y)$, hence
the triplet $b=y$, $b^{\prime}=y^{\prime}$ and $f_{b^{\prime}}=f_{y^{\prime}}$
is stored either in $\mathsf{L}_{\mathsf{{AH}}}(w)$ or in
$\mathsf{L}_{\mathsf{{AH}}}(y)$. The same label also includes
$\mathsf{CID}(y^{\prime},G\setminus T[s,y])$, so (1) follows. We also find
there the value
$\mathsf{conn}(y^{\prime},par(y),G\setminus\\{{y,f_{y^{\prime}}}\\})$. Note
that if $f_{y^{\prime}}=x$, then (2) follows as well. Assume now that
$f_{y^{\prime}}\neq x$. By Observation 3.2, the path $P_{y^{\prime},s,y}$ is
of the form $Q\circ T[f_{y^{\prime}},s]$ where $Q$ avoids $T[s,y]$. We now
observe that $f_{y^{\prime}}\notin T[s,x)$: this follows as otherwise, the
$w$-$s$ path given by $T[w,y^{\prime}]\circ Q\circ T[f_{y^{\prime}},s]$ is
failure-free, contradicting (C2). As $f_{y^{\prime}}$ is, by definition, a
vertex in $T[s,y)$, it follows that $f_{y^{\prime}}\in T(x,y)$. The
$y^{\prime}$-$par(y)$ path $Q\circ T[f_{y^{\prime}},par(y)]$ now certifies
that $y^{\prime},par(y)$ are $xy$-connected, which gives (2). See illustration
in Figure 3. ∎

[scale=0.5]fig_dep_ah.pdf

Figure 3:  Illustration of the proof of Claim 3.4. The tree path from $s$ to
$w$ is shown sideways, where the depth increases from left to right. The path
$Q$ appears in green.

We next show how to use Claim 3.4 for determining the $xy$-connectivity of
$u,v$. The proof divides into three cases according to the ancestry relations
between $u$, $v$ and $y$.

Case 1: Neither of $u,v$ is a descendant of $y$. Then $y\notin T[u,v]$. Since
both $u,v\in T_{h(x)}$, also $x\notin T[u,v]$. Thus $u,v$ are $xy$-connected,
and we are done.

Case 2: Only one of $u,v$ is a descendant of $y$. W.l.o.g., assume the
descendant is $u$. Then $y\neq h(x)$, as otherwise $v$ would also be a
descendant of $y$. It follows that $par(y)\in T_{h(x)}$. Hence
$T[par(y),v]\subseteq T_{h(x)}$, so it avoids $x$. It also avoids $y$, as
$T[par(y),v]$ contains only ancestors of $par(y)$ or of $v$. Thus, $v,par(y)$
are $xy$-connected. Finally, we use Claim 3.4(2) with $w=u$ to determine the
$xy$-connectivity of $u,par(y)$, or equivalently of $u,v$.

Case 3: Both $u,v$ are descendants of $y$. We apply Claim 3.4 twice, with
$w=u$ and $w=v$. Using (2), we check for both $u$ and $v$ if they are
$xy$-connected to $par(y)$. The only situation in which we cannot infer the
$xy$-connectivity of $u,v$ is when both answers are negative. When this
happens, we exploit (1) and compare the component IDs of $u,v$ in $G\setminus
T[s,y]$. If they are equal, then clearly $u,v$ are $xy$-connected as $x,y\in
T[s,y]$. Otherwise, we assert that we can safely determine that $u,v$ are
$xy$-disconnected.

######  Claim 3.5.

If (i) both $u$ and $v$ are $xy$-disconnected from $par(y)$, and (ii) $u$ and
$v$ are $T[s,y]$-disconnected, then $u,v$ are $xy$-disconnected.

###### Proof.

Assume towards a contradiction that there exists a $u$-$v$ path $P$ in
$G\setminus\\{{x,y}\\}$. By (ii), $P$ must intersect $T[s,y]$. Let $a$ be a
vertex in $P\cap T[s,y]$. As $a\notin\\{x,y\\}$, it holds that either $a\in
T[s,x)$ or $a\in T(x,y)$. If $a\in T[s,x)$, then the path $P[u,a]\circ T[a,s]$
connects $u$ to $s$ in $G\setminus\\{{x,y}\\}$, but this contradicts (C2). If
$a\in T(x,y)$, then the path $P[u,a]\circ T[a,par(y)]$ connects $u$ to
$par(y)$ in $G\setminus\\{{x,y}\\}$, contradicting (i). ∎

This concludes the decoding algorithm for the (AH) case, and proves:

######  Lemma 3.6.

There exist $O(\log^{2}n)$-bit labels $\mathsf{L}_{\mathsf{{AH}}}$ supporting
the all-heavy (AH) case.

####  3.3.2 The General Dependent-Failures Case

We assume w.l.o.g. that $y$ is a descendant888We can check this using the
extended IDs, and swap the roles of $x$ in $y$ if needed. of $x$ in $T$.
Condition (C2) implies that both $u$ and $v$ are also descendants of $x$.
Recall that our general strategy is reducing to the (AH) case, as follows.
First, the case where $y$ is not in $T_{h(x)}$ is handled by using 1-VFT
labels _in the graph $G\setminus\\{{x}\\}$_, which enable us to determine
directly whether $u,v$ are connected in
$(G\setminus\\{{x}\\})\setminus\\{y\\}=G\setminus\\{{x,y}\\}$. In the
remaining case where $y\in T_{h(x)}$, we show how to “replace” $u,v$ by _$xy$
-analogs_: vertices $\widehat{u},\widehat{v}$ that are $xy$-connected to $u,v$
(respectively), and lie inside $T_{h(x)}$. Thus, the query
$\langle\widehat{u},\widehat{v},x,y\rangle$ is an analogous (AH)-query to
answer.

##### Construction of $\mathsf{L}_{\mathsf{{dep}}}$ Labels.

The construction is based on defining, for any given vertex $a$ and ancestor
$b$ of $a$, a small set of vertices from $T_{h(b)}$, serving as candidates to
be $bc$-analogs of $a$ for _any_ $c\in T_{h(b)}$.

######  Definition 3.2 (Analog Sets).

For $a,b\in V$ such that $b$ is an ancestor of $a$ in $T$, the _analog set_
$\mathsf{AnSet}(a,b)$ consists of two (arbitrary) distinct vertices
$c_{1},c_{2}$ with the following property: $c_{i}\in T_{h(b)}$ and there
exists an $a$-$c_{i}$ path avoiding $T_{h(b)}^{+}\setminus\\{c_{i}\\}$. If
there is only one such vertex, then $\mathsf{AnSet}(a,b)$ is the singleton
containing it, and if there are none then $\mathsf{AnSet}(a,b)=\emptyset$.

The $\mathsf{L}_{\mathsf{{dep}}}$ labels are constructed by Algorithm 4. We
use the notation $\mathsf{L}_{\mathsf{{1F}}}(a,G^{\prime})$ to denote the
$1$-VFT label of $a\in V$ from Theorem 1.1 _constructed w.r.t the subgraph
$G^{\prime}\subseteq G$_. The label length of $O(\log^{3}n)$ bits follows by
Lemma 1.5, Theorem 1.1 and Lemma 3.6.

1 store $\mathsf{L}_{\mathsf{{AH}}}(a)$;

2 for  _each $b^{\prime}\in I(a)$ with $par(b^{\prime})=b$_ do

3 store vertices $b,b^{\prime}$;

4 store $\mathsf{L}_{\mathsf{{1F}}}(a,G\setminus\\{{b}\\})$,
$\mathsf{L}_{\mathsf{{1F}}}(b^{\prime},G\setminus\\{{b}\\})$;

5 store vertex set $\mathsf{AnSet}(a,b)$, and
$\mathsf{L}_{\mathsf{{AH}}}(c_{i})$ for each $c_{i}\in\mathsf{AnSet}(a,b)$;

6 store $\mathsf{CID}(a,G\setminus T_{h(b)}^{+})$;

7

Algorithm 4 Construction of label $\mathsf{L}_{\mathsf{{dep}}}(a)$ for vertex
$a$

##### Decoding Algorithm for Dependent Failures.

Assume we are given a dependent-failures query $\langle u,v,x,y\rangle$ where
$y$ is a descendant of $x$, along with the $\mathsf{L}_{\mathsf{{dep}}}$
labels. We first treat the easier case where $x$ is a light ancestor of $y$
using the $1$-VFT labels in $G\setminus\\{{x}\\}$.

Case: $x$ is a light ancestor of $y$. Then the child $x_{y}$ of $x$ on the
path $T[x,y]$ is light, hence $x_{y}\in I(y)$. Therefore, the label of $y$
contains the $1$-VFT label
$\mathsf{L}_{\mathsf{{1F}}}(y,G\setminus\\{{x}\\})$. Let $x_{u}$ be the child
of $x$ on the path $T[x,u]$, and define

$\widetilde{u}=\begin{cases}\text{if $x_{u}$ is light:}&u,\\\ \text{if $x_{u}$
is heavy:}&x_{u}=h(x).\end{cases}$

######  Claim 3.7.

It holds that (i) $\widetilde{u}$ is $xy$-connected to $u$, and (ii) one can
find $\mathsf{L}_{\mathsf{{1F}}}(\widetilde{u},G\setminus\\{{x}\\})$.

###### Proof.

If $x_{u}$ is light: Then (i) is trivial. For (ii), note that $x_{u}\in I(u)$,
hence the $1$-VFT label of $\widetilde{u}=u$ with respect to
$G\setminus\\{{x}\\}$, which is
$\mathsf{L}_{\mathsf{{1F}}}(u,G\setminus\\{{x}\\})$, is stored in
$\mathsf{L}_{\mathsf{{dep}}}(u)$.

If $x_{u}$ is heavy: Then $x_{u}\neq x_{y}$, hence the path $T[x_{u},u]$ is
failure-free, which proves (i). For (ii), note that $x_{u}=h(x)\in I(x)$,
hence the $1$-VFT label of $\widetilde{u}=h(x)$ with respect to
$G\setminus\\{{x}\\}$, which is
$\mathsf{L}_{\mathsf{{1F}}}(h(x),G\setminus\\{{x}\\})$, is stored in
$\mathsf{L}_{\mathsf{{dep}}}(x)$. ∎

We define $\widetilde{v}$ and find its $1$-VFT label with respect to
$G\setminus\\{{x}\\}$ in a similar fashion. Finally, we use the $1$-VFT labels
to answer the _single failure_ query
$\langle\widetilde{u},\widetilde{v},y\rangle$ with respect to the graph
$G\setminus\\{{x}\\}$, which determines the $xy$-connectivity of
$\widetilde{u},\widetilde{v}$, or equivalently of $u,v$. So in this case, the
decoding algorithm directly determine the $xy$-connectivity of $u,v$, and we
are done.

From now on, we assume that $x$ is a heavy ancestor of $y$, or equivalently
that $y\in T_{h(x)}$.

Replacing $u,v$ with their $xy$-analogs. In the following, we restrict our
attention to $u$ (and the same can be applied to $v$). Again, let $x_{u}$ be
the child of $x$ on $T[s,u]$. The $xy$-analog $\widehat{u}$ of $u$ is defined
as:

$\widehat{u}=\begin{cases}\text{if $x_{u}$ is heavy:}&u,\\\ \text{if $x_{u}$
is light and
$\mathsf{AnSet}(u,x)\setminus\\{y\\}\neq\emptyset$:}&c\in\mathsf{AnSet}(u,x)\setminus\\{y\\},\\\
\text{if $x_{u}$ is light and
$\mathsf{AnSet}(u,x)\setminus\\{y\\}=\emptyset$:}&\text{undefined.}\end{cases}$

The corner case where $\widehat{u}$ is undefined can be alternatively
described as follows:

  1. (C4)

$x_{u}$ is light, and no $c\in T_{h(x)}\setminus\\{y\\}$ is connected to $u$
by a path internally avoiding $T_{h(x)}^{+}$.

The key observation for handling case (C4) is:

######  Claim 3.8.

If (C4) holds, then:

(1) For any vertex $c\in T_{h(x)}\setminus\\{y\\}$, $u$ and $c$ are
$xy$-disconnected.

(2) For any vertex $c\notin T_{h(x)}\cup\\{x,y\\}$, $u$ and $c$ are
$xy$-connected iff they are $T_{h(x)}^{+}$-connected.

###### Proof.

For (1), assume towards a contradiction that there exists a $u$-$c$ path $P$
in $G\setminus\\{{x,y}\\}$. Let $c^{\prime}$ be the first (closest to $u$)
vertex from $T_{h(x)}$ appearing in $P$. Since $c^{\prime}\neq y$, and the
subpath $P[u,c^{\prime}]$ internally avoids $T_{h(x)}^{+}$, we get a
contradiction to (C4).

The “if” direction of (2) is trivial as $\\{x,y\\}\subseteq T_{h(x)}^{+}$. For
the “only if” direction, let $P$ be a $u$-$c$ path in $G\setminus\\{{x,y}\\}$.
It suffices to prove that $P$ avoids $T_{h(x)}$, but this follows directly
from (1). ∎

We handle case (C4) as follows. If $v\in T_{h(x)}$, then by Claim 3.8(1) we
determine that $u,v$ are $xy$-disconnected, and we are done. Else, the child
$x_{v}$ of $x$ on $T[x,v]$ is light, hence $x_{v}\in I(v)$. Therefore
$\mathsf{L}_{\mathsf{{dep}}}(v)$ contains $\mathsf{CID}(v,G\setminus
T_{h(x)}^{+})$ (set $a=v$, $b=x$ and $b^{\prime}=x_{v}$). As $x_{u}$ is also
light by (C4), we can find $\mathsf{CID}(u,G\setminus T_{h(x)}^{+})$ in a
similar fashion. By Claim 3.8(2), comparing these $\mathsf{CID}$s allows us to
determine the $xy$-connectivity of $u,v$, and we are done again.

If the corner case (C4) does not hold, then $\widehat{u}$ is indeed a valid
$xy$-analog of $u$. Namely:

######  Claim 3.9.

If $\widehat{u}$ is defined, then (i) $\widehat{u}\in T_{h(x)}$, (ii)
$u,\widehat{u}$ are $xy$-connected, and (iii) one can find the label
$\mathsf{L}_{\mathsf{{AH}}}(\widehat{u})$.

###### Proof.

If $x_{u}$ is heavy: Then (i) and (ii) are trivial. For (iii) we simply note
that $\mathsf{L}_{\mathsf{{dep}}}(u)$ stores $\mathsf{L}_{\mathsf{{AH}}}(u)$.

If $x_{u}$ is light and $\mathsf{AnSet}(u,x)\setminus\\{y\\}\neq\emptyset$:
Then $\widehat{u}\in\mathsf{AnSet}(u,x)\setminus\\{y\\}$. By definition of
$\mathsf{AnSet}(u,x)$ it holds that $\widehat{u}\in T_{h(x)}$, which gives
(i), and that there is a $u$-$\widehat{u}$ path avoiding
$T_{h(x)}^{+}\setminus\\{\widehat{u}\\}$, and consequently also $\\{x,y\\}$,
which gives (ii). For (iii), we note that as $x_{u}$ is light it holds that
$x_{u}\in I(u)$. Thus, $\mathsf{L}_{\mathsf{{dep}}}(u)$ stores the
$\mathsf{L}_{\mathsf{{AH}}}$ labels of the vertices in $\mathsf{AnSet}(u,x)$,
and in particular stores $\mathsf{L}_{\mathsf{{AH}}}(\widehat{u})$. ∎

Finalizing. We have shown a procedure that either determines directly the
$xy$-connectivity of $u,v$, or certifies that $y\in T_{h(x)}$ and finds
$xy$-analogs $\widehat{u},\widehat{v}\in T_{h(x)}$ of $u,v$ (respectively)
along with their (AH)-labels
$\mathsf{L}_{\mathsf{{AH}}}(\widehat{u}),\mathsf{L}_{\mathsf{{AH}}}(\widehat{v})$.
In the latter case, we answer the (AH)-query
$\langle\widehat{u},\widehat{v},x,y\rangle$ using the
$\mathsf{L}_{\mathsf{{AH}}}$ labels999$\mathsf{L}_{\mathsf{{AH}}}(x)$ and
$\mathsf{L}_{\mathsf{{AH}}}(y)$ are stored in $\mathsf{L}_{\mathsf{{dep}}}(x)$
and $\mathsf{L}_{\mathsf{{dep}}}(y)$ respectively. and determine the
$xy$-connectivity of $\widehat{u},\widehat{v}$, or equivalently of $u,v$. This
concludes the decoding algorithm for dependent failures. We therefore have:

######  Lemma 3.10.

There exists $O(\log^{3}n)$-bit labels $\mathsf{L}_{\mathsf{{dep}}}$
supporting the dependent failures case.

By combining the $\mathsf{L}_{\mathsf{{dep}}}$ labels of Lemma 3.10 with the
$\mathsf{L}_{\mathsf{{ind}}}$ labels of Lemma 3.3, we obtain the $2$-VFT
labels of Theorem 1.2. The preprocessing time analysis, which completes the
proof of Theorem 1.2, is found in Appendix A.

##  4 Sublinear $f$-VFT Labels

In this section, we provide an $f$-VFT labeling scheme with sublinear size for
any $f=o(\log\log n)$. Note that labels of near-linear size are directly
obtained by the $f$-EFT labeling scheme of [DP21] (e.g., by including in the
labels of a vertex, the EFT-labels of all its incident edges). We show:

######  Theorem 4.1 ($f$-VFT Labels with Sublinear Size).

For every $n$-vertex graph $G=(V,E)$ and fixed parameter $f=o(\log\log n)$,
there is a polynomial time randomized algorithm for computing $f$-VFT labels
of size $\widetilde{O}(n^{1-1/2^{f-2}})$. For every query $\langle
u,v,F\rangle$ for $F\subseteq V$, $|F|\leq f$, the correctness holds w.h.p.

We use the EFT-labeling scheme of Dory and Parter [DP21], whose label size is
independent in the number of faults. The correctness guarantee holds w.h.p.
for a _polynomial_ number of queries.

######  Theorem 4.2 (Slight Restatement of Theorem 3.7 in [DP21]).

For every undirected $n$-vertex graph $G=(V,E)$, there is a randomized EFT
connectivity labeling scheme with labels $\mathsf{EL}:V\cup
E\to\\{0,1\\}^{\ell}$ of length $\ell=O(\log^{3}n)$ bits (independent in the
number of faults). For a given triplet along w the $\mathsf{EL}$ labels of
$u,v\in V$ and every edge set $F\subseteq E$, the decoding algorithm
determines, w.h.p., if $u$ and $v$ are connected in $G\setminus F$.

##### The Labels.

Our starting observation is that one can assume, w.l.o.g., that $|E(G)|\leq
fn$ edges. This holds as it is always sufficient to apply the labeling scheme
on the sparse $f$ (vertex) connectivity certificate of $G$, which has at most
$fn$ edges, see e.g., [CKT93]. The labeling scheme is inductive where the
construction of $f$-VFT labels is based on the construction of $(f-1)$ VFT
labels given by the induction assumption. For the base of the induction
($f=2$), we use the $2$-VFT labels of Theorem 1.2. The approach is then based
on dividing the vertices into high-degree and low-degree vertices based on a
degree threshold $\Delta=2f\cdot n^{1-1/2^{f-2}}$. Formally, let $V_{H}$ be
all vertices with degree at least $\Delta$. By our assumption, the number of
high-degree vertices is at most $|V_{H}|\leq O(fn/\Delta)$. Letting
$\mathsf{EL}(\cdot)$ denote that $f$-EFT labeling scheme of Theorem 4.2 by
[DP21], the $f$-VFT label of $v$ is given by Algorithm 5.

1 store $\mathsf{EL}(v)$;

2 for  _each $x\in V_{H}$_ do

3 store $\mathsf{VL}_{\mathsf{{f-1}}}(v,G\setminus\\{{x}\\})$;

4

5if  _$v\in V\setminus V_{H}$_ then

6 store $\mathsf{EL}(e=(u,v))$ for every adjecent edge $(u,v)\in G$;

7

Algorithm 5 Construction of label $\mathsf{VL}_{\mathsf{{f}}}(v)$ of for
vertex $v$

##### The Decoding Algorithm.

Consider a query $\langle u,v,F\rangle\in V\times V\times V^{\leq f}$. We
distinguish between two cases, based on the degrees of the faults $F$ in the
graph $G$. Assume first that there exists at least one high-degree vertex
$x\in F\cap V_{H}$. In this case, the labels of every
$w\in\\{u,v\\}\cup(F\setminus\\{x\\})$ includes the $(f-1)$ VFT label in
$G\setminus\\{x\\}$, namely,
$\mathsf{VL}_{\mathsf{{f-1}}}(v,G\setminus\\{w\\})$. We can then determine the
$F$-connectivity of $u$,$v$ using the decoding algorithm of the $(f-1)$-VFT
labels (given by the induction assumption). It remains to consider the case
where all vertices have low-degrees. In this case, the VFT-labels include the
EFT-labels of $u,v$, and all failed edges, incident to the failed vertices.
This holds as the label of every failed vertex $x\in F$ contains
$\mathsf{EL}(e=(x,z))$ for each of its incident edges $(x,z)$ in $G$. This
allows us to apply the decoding algorithm of Theorem 4.1 in a black-box
manner.

##### Label Size.

We now turn to bound the label size. For every $f\leq n$, let
$\sigma_{V}(f,n),\sigma_{E}(n)$ be an upper bound on $f$-VFT (resp., EFT)
labels for $n$-vertex graphs. Assume by induction on $g\leq f-1$ that

$\sigma_{V}(g,n)=2^{g-2}\cdot g\cdot n^{1-1/2^{g-2}}\cdot c\cdot\log^{3}n~{},$
(4.1)

where $c\cdot\log^{3}n$ is the bound on the EFT labels of Theorem 4.2. This
clearly holds for $g=2$ (by Theorem 1.2). Denote the length of the $f$-VFT
label for vertex $v$ by $|\mathsf{VL}_{\mathsf{{f}}}(v)|$. By taking
$\Delta(f,n)=2f\cdot n^{1-1/2^{f-2}}$ to be the degree threshold $\Delta$ in
our $f$-VFT label construction, and using Eq. (4.1), we have:

$|\mathsf{VL}_{\mathsf{{f}}}(v)|\leq\sigma_{V}(f-1,n-1)\cdot(2nf/\Delta(f,n))+\Delta(f,n)\cdot\sigma_{E}(f,n)~{}\leq\sigma_{V}(f,n)~{}.$

This satisfies the induction step and provides a bound of
$\sigma_{V}(f,n)=\widetilde{O}(n^{1-1/2^{f-2}})$ for every $f=o(\log\log n)$,
as desired. Theorem 4.1 follows.

##### Acknowledgments.

We would like to thank Michal Dory for useful discussions.

## References

  * [ACG12] Ittai Abraham, Shiri Chechik, and Cyril Gavoille.  Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1199–1218, 2012.
  * [ACGP16] Ittai Abraham, Shiri Chechik, Cyril Gavoille, and David Peleg.  Forbidden-set distance labels for graphs of bounded doubling dimension.  ACM Trans. Algorithms, 12(2):22:1–22:17, 2016.
  * [AGM12] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 459–467. SIAM, 2012.
  * [BCHR18] Surender Baswana, Keerti Choudhary, Moazzam Hussain, and Liam Roditty.  Approximate single source fault tolerant shortest path.  In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1901–1915. SIAM, 2018.
  * [BT89] Giuseppe Di Battista and Roberto Tamassia.  Incremental planarity testing (extended abstract).  In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 436–441. IEEE Computer Society, 1989.
  * [BT96] Giuseppe Di Battista and Roberto Tamassia.  On-line maintenance of triconnected components with spqr-trees.  Algorithmica, 15(4):302–318, 1996.
  * [CD17] Keren Censor-Hillel and Michal Dory.  Fast distributed approximation for TAP and 2-edge-connectivity.  In 21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18-20, 2017, pages 21:1–21:20, 2017.
  * [Cho16] Keerti Choudhary.  An optimal dual fault tolerant reachability oracle.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 130:1–130:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.
  * [Cho22] Keerti Choudhary.  Personal communication.  2022\.
  * [CKT93] Joseph Cheriyan, Ming-Yang Kao, and Ramakrishna Thurimella.  Scan-first search and sparse certificates: an improved parallel algorithm for k-vertex connectivity.  SIAM Journal on Computing, 22(1):157–174, 1993.
  * [CT07] Bruno Courcelle and Andrew Twigg.  Compact forbidden-set routing.  In STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, pages 37–48, 2007.
  * [DGJ20] Maciej Duleba, Pawel Gawrychowski, and Wojciech Janczewski.  Efficient labeling for reachability in directed acyclic graphs.  In Yixin Cao, Siu-Wing Cheng, and Minming Li, editors, 31st International Symposium on Algorithms and Computation, ISAAC 2020, December 14-18, 2020, Hong Kong, China (Virtual Conference), volume 181 of LIPIcs, pages 27:1–27:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [DP09] Ran Duan and Seth Pettie.  Dual-failure distance and connectivity oracles.  In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 506–515. SIAM, 2009.
  * [DP16] Ran Duan and Seth Pettie.  Connectivity oracles for graphs subject to vertex failures.  CoRR, abs/1607.06865, 2016.
  * [DP17] Ran Duan and Seth Pettie.  Connectivity oracles for graphs subject to vertex failures.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 490–509, 2017.
  * [DP20] Ran Duan and Seth Pettie.  Connectivity oracles for graphs subject to vertex failures.  SIAM J. Comput., 49(6):1363–1396, 2020.
  * [DP21] Michal Dory and Merav Parter.  Fault-tolerant labeling and compact routing schemes.  In Avery Miller, Keren Censor-Hillel, and Janne H. Korhonen, editors, PODC ’21: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, July 26-30, 2021, pages 445–455. ACM, 2021\.
  * [FNY+20] Sebastian Forster, Danupon Nanongkai, Liu Yang, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Computing and testing small connectivity in near-linear time and queries via fast local cut algorithms.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2046–2065. SIAM, 2020.
  * [GILP15] Loukas Georgiadis, Giuseppe F. Italiano, Luigi Laura, and Nikos Parotsidis.  2-vertex connectivity in directed graphs.  In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 605–616. Springer, 2015.
  * [GK17] Manoj Gupta and Shahbaz Khan.  Multiple source dual fault tolerant BFS trees.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 127:1–127:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [GKKT15] David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn.  Dynamic graph connectivity with improved worst case update time and sublinear space.  CoRR, abs/1509.06464, 2015.
  * [GMW20] Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Minimum cut in o(m log2 n) time.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 57:1–57:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [GNT20] Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup.  Faster algorithms for edge connectivity via random 2-out contractions.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1260–1279. SIAM, 2020.
  * [GP16] Mohsen Ghaffari and Merav Parter.  MST in log-star rounds of congested clique.  In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 19–28, 2016.
  * [GT12] Loukas Georgiadis and Robert Endre Tarjan.  Dominators, directed bipolar orders, and independent spanning trees.  In Artur Czumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part I, volume 7391 of Lecture Notes in Computer Science, pages 375–386. Springer, 2012.
  * [HLW21] Zhiyang He, Jason Li, and Magnus Wahlström.  Near-linear-time, optimal vertex cut sparsifiers in directed acyclic graphs.  In Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, 2021, Lisbon, Portugal (Virtual Conference), volume 204 of LIPIcs, pages 52:1–52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [HT73] John E. Hopcroft and Robert Endre Tarjan.  Dividing a graph into triconnected components.  SIAM J. Comput., 2(3):135–158, 1973.
  * [Kar93] David R. Karger.  Global min-cuts in rnc, and other ramifications of a simple min-cut algorithm.  In Vijaya Ramachandran, editor, Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 25-27 January 1993, Austin, Texas, USA, pages 21–30. ACM/SIAM, 1993.
  * [KB10] Neelesh Khanna and Surender Baswana.  Approximate shortest paths avoiding a failed vertex: Optimal size data structures for unweighted graph.  In 27th International Symposium on Theoretical Aspects of Computer Science-STACS 2010, pages 513–524, 2010.
  * [KKM13] Bruce M Kapron, Valerie King, and Ben Mountjoy.  Dynamic graph connectivity in polylogarithmic worst case time.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1131–1142. SIAM, 2013.
  * [KNR92] Sampath Kannan, Moni Naor, and Steven Rudich.  Implicit representation of graphs.  SIAM Journal on Discrete Mathematics, 5(4):596–603, 1992.
  * [KTBC91] Arkady Kanevsky, Roberto Tamassia, Giuseppe Di Battista, and Jianer Chen.  On-line maintenance of the four-connected components of a graph (extended abstract).  In 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991, pages 793–801. IEEE Computer Society, 1991.
  * [LNP+21] Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Vertex connectivity in poly-logarithmic max-flows.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 317–329. ACM, 2021.
  * [NMN01] Jaroslav Nešetřil, Eva Milková, and Helena Nešetřilová.  Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history.  Discrete Mathematics, 233(1):3–36, 2001.
  * [NN93] Joseph Naor and Moni Naor.  Small-bias probability spaces: Efficient constructions and applications.  SIAM journal on computing, 22(4):838–856, 1993.
  * [NSY19] Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai.  Breaking quadratic time for small vertex connectivity and an approximation scheme.  In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 241–252. ACM, 2019.
  * [Par15] Merav Parter.  Dual failure resilient bfs structure.  In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, pages 481–490, 2015.
  * [Par19] Merav Parter.  Small cuts and connectivity certificates: A fault tolerant approach.  In 33rd International Symposium on Distributed Computing, 2019.
  * [Par20] Merav Parter.  Distributed constructions of dual-failure fault-tolerant distance preservers.  In Hagit Attiya, editor, 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, volume 179 of LIPIcs, pages 21:1–21:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [Pel00] David Peleg.  Distributed Computing: A Locality-sensitive Approach.  SIAM, 2000.
  * [PP22] Merav Parter and Asaf Petruschka.  Near-optimal distributed computation of small vertex cuts.  In 36nd International Symposium on Distributed Computing DISC, 2022.
  * [PT11] David Pritchard and Ramakrishna Thurimella.  Fast computation of small cuts via cycle space sampling.  ACM Transactions on Algorithms (TALG), 7(4):46, 2011.
  * [PY21] Seth Pettie and Longhui Yin.  The structure of minimum vertex cuts.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 105:1–105:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [ST83] Daniel Dominic Sleator and Robert Endre Tarjan.  A data structure for dynamic trees.  J. Comput. Syst. Sci., 26(3):362–391, 1983.
  * [Vad12] Salil P. Vadhan.  Pseudorandomness.  Foundations and Trends® in Theoretical Computer Science, 7(1–3):1–336, 2012.
  * [Wes00] Douglas B. West.  Introduction to Graph Theory.  Prentice Hall, 2 edition, September 2000.

##  Appendix A Preprocessing Times

##### Preprocessing Time for $1$-VFT Labels (Theorem 1.1).

We start by computing a $2$-vertex connectivity certificates
$G^{\prime}\subseteq G$ such that $|E(G^{\prime})|=O(n)$, which can be done in
$O(m)$ time by [CKT93]. We then apply the labeling algorithm on the graph
$G^{\prime}$. It is easy to see that each label
$\mathsf{L}_{\mathsf{{1F}}}(v)$ can be computed by applying $\widetilde{O}(1)$
connectivity algorithms, hence taking $\widetilde{O}(n)$ time. This completes
the deterministic construction of Theorem 1.1. The linear-time randomized
computation, in fact, follows by our distributed computation of these labels
which are based on [PP22], is deferred to Appendix B.

##### Preprocessing Time for $2$-VFT Labels (Theorem 1.2).

We start by computing a $3$-vertex connectivity certificates
$G^{\prime}\subseteq G$ such that $|E(G^{\prime})|=O(n)$, which can be done in
$O(m)$ time by [CKT93]. We then apply the labeling algorithm on the graph
$G^{\prime}$. The first step is to compute the single-source $2$-VFT labels of
[Cho16], which can be done in
$O(|V(G^{\prime})|\cdot|E(G^{\prime})|)=O(n^{2})$ time overall [Cho22]. Next,
it is easy to see that each label $\mathsf{L}_{\mathsf{{ind}}}(v)$ or
$\mathsf{L}_{\mathsf{{dep}}}(v)$ can be computed by applying
$\widetilde{O}(1)$ connectivity algorithms and specific $1$-VFT label
constructions, each taking $\widetilde{O}(n)$ time. This completes the proof
of Theorem 1.2.

##  Appendix B Distributed Computation of Labels and Cut Vertices

We now turn to describe distributed computation of our $1$-VFT labels in the
congest model of distributed computing [Pel00]. In this model, the
communication is abstracted as an $n$-vertex graph $G=(V,E)$. Each vertex
holds a unique identifier of $O(\log n)$ bits. The algorithm works in
synchronous rounds, where in each round, a vertex can exchange $O(\log n)$-bit
messages with each of its neighbors. In [PP22], the authors describe a
distributed algorithm for detecting single vertex cuts. The exact same
algorithm can also provide $1$-VFT labels. For the sake of completeness, we
describe the algorithm here.

###  B.1 Graph Sketches

The algorithm is based on the notion of _graph sketches_. The implementation
of the graph sketches technique calls for providing each of the graph edges
with _convenient_ identifiers that ease the subsequent connectivity algorithms
(in which these sketches get used). We start by defining these identifiers and
then provide the formal sketch definition.

##### Extended Edge Identifiers [GP16, DP21].

The decoding of the sketch information requires one to distinguish between an
identifier of a single edge to the bitwise XOR of several edges. For this
purpose, we define for each edge $e$ an extended edge identifier
$\operatorname{EID}_{T}(e)$ that allows distinguishing between these cases,
and serves as the identifier of the edge. The extended edge identifier
$\operatorname{EID}_{T}(e)$ consists of a (randomized) unique distinguishing
identifier $\operatorname{UID}(e)$, as well as additional tree related
information. The computation of $\operatorname{UID}(e)$ is based on the notion
of $\epsilon$-_bias_ sets [NN93]. The construction is randomized and
guarantees that, w.h.p., the XOR of the $\operatorname{UID}$ part of each
given subset of edges $S\subseteq E$, for $|S|\geq 2$, is not a legal
$\operatorname{UID}$ identifier of any edge. Let $\mathsf{XOR}(S)$ be the
bitwise XOR of the extended identifiers of edges in $S$, i.e.,
$\mathsf{XOR}(S)=\oplus_{e\in S}\operatorname{EID}_{T}(e)$. In addition, let
$\mathsf{XOR}_{U}(S)=\oplus_{e\in S}\operatorname{UID}(e)$.

######  Lemma B.1 (Modification of Lemma 2.4 in [GP16]).

There is an $\widetilde{O}(D)$-round algorithm that sends all nodes a random
seed $\mathcal{S}_{ID}$ of $O(\log^{2}n)$ bits. Using this seed, all nodes
locally define a (consistent) collection
$\mathcal{I}=\\{\operatorname{UID}(e_{1}),\ldots,\operatorname{UID}(e_{M})\\}$
of $M=\binom{n}{2}$ random identifiers for all possible edges $(u,v)$, each of
$O(\log n)$-bits. These identifiers are such that for each subset
$E^{\prime}\subseteq E$, where $|E^{\prime}|\neq 1$, we have
$\Pr[\mathsf{XOR}_{U}(E^{\prime})\in\mathcal{I}]\leq 1/n^{10}$. In addition,
given the identifiers $\operatorname{ID}(u),\operatorname{ID}(v)$ of the edge
$e=(u,v)$ endpoints, and the seed $\mathcal{S}_{ID}$, one can determine
$\operatorname{UID}(e)$ in $\widetilde{O}(1)$ time.

The extended identifier $\operatorname{EID}_{T}(e)$ is given by

$\operatorname{EID}_{T}(e)=[\operatorname{UID}(e),\operatorname{ID}(u),\operatorname{ID}(v),\mathsf{ANC}_{T}(u),\mathsf{ANC}_{T}(v)]~{}.$
(B.1)

The identifiers of $\operatorname{ID}(u),\operatorname{ID}(v)$ are used in
order to verify the validity of the unique identifier $\operatorname{UID}(e)$.
When the tree $T$ is clear from the context, we might omit it and simply write
$\operatorname{EID}(e)$.

##### Defining Graph Sketches.

Graph sketches are a tool to identify outgoing edges. The sketches are based
on random sub-sampling of the graph edges with logarithmic number of scales,
i.e., with probability of $2^{-j}$ for every $j\in[0,\log m]$. We follow
[DP16, DP17] and use pairwise independent hash functions to decide whether to
include edges in sampled sets.

Choose $L=c\log n$ pairwise independent hash functions
$h_{1},\ldots,h_{L}:\\{0,1\\}^{\Theta(\log n)}\to\\{0,\ldots,2^{\log m}-1\\}$,
and for each $i\in\\{1,\ldots,L\\}$ and $j\in[0,\log m]$, define the edge set
$E_{i,j}=\\{e\in E~{}\mid h_{i}(e)\in[0,2^{\log m-j})\\}~{}.$ Each of these
hash functions $h_{i}$ can be defined using a random seed
$\mathcal{S}_{h_{i}}$ of logarithmic length [Vad12]. Thus, a random seed
$\mathcal{S}_{\mathcal{H}}$ of length $O(L\log n)$ can be used to determine
the collection of all these $L$ functions.

As observed in [DP16, GKKT15], pairwise independence is sufficient to
guarantee that for any non-empty set $E^{\prime}\subset E$ and any $i$, there
exists an index $j$, such that with constant probability
$\mathsf{XOR}(E^{\prime}\cap E_{i,j})$ is the name (extended identifier) of
one edge in $E^{\prime}$, for a proof see Lemma 5.2 in [GKKT15]. Hence, by
exploiting the structure of the extended IDs, it holds:

######  Lemma B.2.

(i) [Lemma 5.2 in [GKKT15]] For any non-empty edge set $E^{\prime}$ and any
$i$, with constant probability there exists a $j$ satisfying that
$|E^{\prime}\cap E_{i,j}|=1$; (ii) Given the seed $\mathcal{S}_{ID}$, one can
determine in $\widetilde{O}(1)$ time if $\mathsf{XOR}(E^{\prime}\cap E_{i,j})$
corresponds to a single edge ID in $G$ or not, w.h.p.

For each vertex $v$ and indices $i,j$, let $E_{i,j}(v)$ be the edges incident
to $v$ in $E_{i,j}$. The $i^{th}$ _basic sketch unit_ of each vertex $v$ is
then given by:

$\mathsf{Sketch}_{G,i}(v)=[\mathsf{XOR}(E_{i,0}(v)),\ldots,\mathsf{XOR}(E_{i,\log
m}(v))].$ (B.2)

The sketch of each vertex $v$ is defined by a concatenation of $L=\Theta(\log
n)$ basic sketch units:

$\mathsf{Sketch}_{G}(v)=[\mathsf{Sketch}_{G,1}(v),\mathsf{Sketch}_{G,2}(v),\ldots\mathsf{Sketch}_{G,L}(v)]~{}.$

For every subset of vertices $S$, let $\mathsf{Sketch}_{G}(S)=\oplus_{v\in
S}\mathsf{Sketch}_{G}(v).$ When the graph $G$ is clear from the context, we
may omit it and write $\mathsf{Sketch}_{i}(v)$ and $\mathsf{Sketch}(v)$.

######  Lemma B.3.

For any subset $S$, given one basic sketch unit $\mathsf{Sketch}_{i}(S)$ and
the seed $\mathcal{S}_{ID}$ one can compute, with constant probability, an
outgoing edge $E(S,V\setminus S)$ if such exists. The complexity is
$\widetilde{O}(1)$ time.

###  B.2 The Distributed Algorithms

We are now ready to describe the distributed label construction. Throughout,
let $T$ be a BFS tree rooted at some arbitrary vertex $s$. The latter can be
computed in $O(D)$ rounds. By Lemma 2.1 in [CD17], we have:

######  Lemma B.4.

Given a tree $T$, there is an $O(D(T))$-round algorithm for computing ancestry
labels $\mathsf{ANC}_{T}(v)$ of $O(\log^{2}n)$ bits for every $v\in V$, where
$D(T)$ is the depth of the tree $T$.

##### Step (0): Computation of Heavy-Light Tree Decomposition and Extended
IDs.

Given the BFS tree $T$, the heavy-light tree decomposition can be computed in
$O(D)$ rounds. In the distributed output format, each vertex $v$ knows its
heavy child in $T$. By propgating tree edges downwards the tree, each vertex
$v$ can learn its tree path $T[s,v]$ as well as to identify the light edges
(and consequently also the heavy edges) on this path.

It is easy to see that this can be done simply by computing the size of
subtrees $|T_{v}|$ for each vertex $v$. This allows $v$ to determine its heavy
child in $T$. Using Lemma B.4, each vertex can obtain its ancestry label
$\mathsf{ANC}_{T}(v)$. To complete the computation of the extended edge-IDs,
the source $s$ samples a random seed $\mathcal{S}_{ID}$ of $\widetilde{O}(1)$
bits and share it with all vertices. Then, using Lemma B.1, each vertex $v$
can then locally compute the unique edge-ID $\operatorname{UID}(e)$ for each
of its incident edges.

##### Step (1): Computation of Subtree Sketches.

The source $s$ locally samples the collection of $L=O(\log n)$ random seeds
$\mathcal{S}_{\mathcal{H}}=\\{\mathcal{S}_{h}\mid h\in\\{1,\ldots,L\\}\\}$,
and send it to all the vertices. These seeds provide all the required
randomness for the computation of the sketch information. By aggregating the
individual sketch information $\alpha_{u}=\mathsf{Sketch}_{G}(u)$ for every
$u\in V$, from the leaf vertices on $T$ up to the root $s$, each vertex $v$
obtains its subtree sketch, given by
$\mathsf{Sketch}_{G}(V(T_{v}))=\oplus_{u\in T_{v}}\alpha_{u}$. By the end of
this sketch aggregation process, the source $s$ broadcasts its output sketch,
namely $\mathsf{Sketch}_{G}(V)$, to all the vertices in the graph.

##### Step (2): Local Connectivity Computation.

This step is locally applied at every vertex $x$, and requires no additional
communication. We show that each vertex $x$, given the received sketch
information in Step (1), can locally simulate the Borůvka’s algorithm [NMN01]
in the graph $G\setminus\\{x\\}$. Consequently, it can determine if
$G\setminus\\{x\\}$ is connected, as well as assigning each of its children a
unique ID of their connected component in $G\setminus\\{x\\}$. Let
$u_{1},\ldots,u_{d_{x}}$ be the children of $x$ in $T$. The connected
components in $T\setminus\\{x\\}$ are denoted by

$\mathcal{C}_{x}=\\{V(T_{u_{j}}),j\in\\{1,\ldots,d_{x}\\}\\}\cup\\{V\setminus
V(T_{x})\\}.$

Observe that while $x$ does not know all vertices in the components of
$\mathcal{C}_{x}$, it knows (at least) one vertex in each of these components
(i.e., its immediate children and $s$). This allows $x$ to assign each
component in $\mathcal{C}_{x}$ an $O(\log n)$-bit identifier. The ID of the
component containing $s$ will be throughout defined by $\operatorname{ID}(s)$.

By Step (1), $x$ holds the $G$-sketch of each component in $\mathcal{C}_{x}$:
it has explicitly received $\mathsf{Sketch}_{G}(V(T_{u_{j}}))$ from each child
$u_{j}$ for every $j\in\\{1,\ldots,d_{x}\\}$. In addition, it can locally
infer $\mathsf{Sketch}(V\setminus
V(T_{x}))=\mathsf{Sketch}(V)\oplus\mathsf{Sketch}(V(T_{x}))$. To locally
implement the Borůvka’s algorithm on these connected components, it is first
required to update these $G$-sketches into $(G\setminus\\{x\\})$-sketch, as
described next.
(2.1): Obtaining sketch information in $G\setminus\\{x\\}$. Recall that the
seeds $\mathcal{S}_{h}$ determine the sampling of edges into the sketches.
Therefore, as $x$ knows $\mathcal{S}_{h}$ for every $h\in\\{1,\ldots,L\\}$, as
well as, the extended identifiers of its incident edges (from Step (0)), it
can cancel these edges from the respective entries in the sketches of each
component $C\in\mathcal{C}_{x}$. Specifically, to cancel an adjacent edges
$(x,u)\in G$, it first uses the ancestry labels of the edge to determine the
connected component $C$ of $u$ in $\mathcal{C}_{x}$. Then, using the
$\mathcal{S}_{h}$ seeds, it can determine all the sketch entries of
$\mathsf{Sketch}_{G}(C)$ in which $(x,u)$ has been sampled. This allows $x$ to
obtain $\mathsf{Sketch}_{G\setminus\\{x\\}}(C)$ for every
$C\in\mathcal{C}_{x}$.
(2.2): Simulating the Borůvka algorithm in $G\setminus\\{x\\}$. The input to
this step is the identifiers of the components
$\mathcal{C}_{x,0}=\mathcal{C}_{x}$ in $T\setminus\\{x\\}$, along with their
sketch information in $G\setminus\\{x\\}$. The desired output is to determine
a unique component-ID to each child of $x$ in $G\setminus\\{x\\}$. The
algorithm consists of $L=O(\log n)$ phases of the Borůvka algorithm, and works
in an almost identical manner to the (centralized) decoding algorithm of
[DP21]. For completeness, we fully describe it here as well.

Each phase $i\in\\{1,\ldots,L\\}$ will be given as input a partitioning
$\mathcal{C}_{x,i}=\\{C_{i,1},\ldots,C_{i,k_{i}}\\}$ of (not necessarily
maximal) connected components in $G\setminus\\{x\\}$; along with the sketch
information of the components $\mathcal{C}_{x,i}$ in $G\setminus\\{x\\}$. The
output of the phase is a partitioning $\mathcal{C}_{x,i+1}$, along with their
sketch information in $G\setminus\\{x\\}$ and the identifiers of the
components for each child of $x$.

A component $C_{i,j}\in\mathcal{C}_{i,x}$ is denoted as _growable_ if it has
at least one outgoing edge to a vertex in $V\setminus(C_{i,j}\cup\\{x\\})$.
Letting $N_{i}$ denote the number of growable components in $\mathcal{C}_{i}$,
the output partitioning $\mathcal{C}_{i+1}$ of the $i^{th}$ step guarantees
that $N_{i+1}\leq cN_{i}/2$ in expectation for some constant $0<c\leq 1$ (see
Lemma B.3). To obtain outgoings edges from the growable components in
$\mathcal{C}_{x,i}$, the algorithm uses the $i^{th}$ basic-unit sketch
$\mathsf{Sketch}_{i}(C_{i,j})$ of each $C_{i,j}\in\mathcal{C}_{x,i}$. By Lemma
B.3, from every growable component in $\mathcal{C}_{x,i}$, we get one outgoing
edge $e^{\prime}=(u,v)$ with constant probability. Using the extended edge
identifier of $e^{\prime}$ the algorithm can also detect the component
$C_{i,j^{\prime}}$ to which the second endpoint, say $v$, of $e^{\prime}$
belongs using the ancestry label of the detected edge $e^{\prime}$. That
allows us to compute the component of $v$ in the initial partitioning
$T\setminus\\{x\\}$, i.e., the component $C_{q,0}$ of $v$ in
$\mathcal{C}_{x,0}$. Thus $y$ belongs to the unique component
$C_{i,j^{\prime}}\in\mathcal{C}_{i}$ that contains $C_{q,0}$. Note that it is
important to use fresh randomness (i.e., independent sketch information) in
each of the Boruvka phases [AGM12, KKM13, DP16]. The algorithm then computes
the updated sketches of the merged components. For this purpose, each Borůvka
phase $i$ is based on the sketch information obtained with a fresh seed
$\mathcal{S}_{h}$. The sketch information for phase $i+1$ is given by XORing
over the sketches of the components in $\mathcal{C}_{x,i}$ that got merged
into a single component in $\mathcal{C}_{x,i+1}$. In expectation, the number
of growable components is reduced by a constant factor in each phase. Thus
after $L=O(\log n)$ phases, the expected number of growable components is at
most $1/n^{5}$, and using Markov inequality, we conclude that w.h.p there are
no growable components. The final partitioning $\mathcal{C}_{x,L}$
corresponds, w.h.p, to the maximal connected components in
$G\setminus\\{x\\}$.

This local simulation of the Borůvka’s algorithm allows $x$ to deduce the
following useful information. First, it can determine if it is a cut-vertex
which holds, w.h.p., iff $|\mathcal{C}_{x,L}|\geq 2$. In addition, $x$ can
compute a unique component ID for each of its children in $G\setminus\\{x\\}$.
The ID of the component containing $s$ is set to $ID(s)$, and the ID of any
other component in $\mathcal{C}_{x,L}$ (if exists) is set to be the largest ID
among all $x$’s children contained in that component. Within another round of
communication, each vertex $v$ holds its component-ID in
$G\setminus\\{par(v)\\}$. We denote this value by $\mathsf{CID}(v)$, namely
$\mathsf{CID}(v):=\mathsf{CID}(v,G\setminus\\{{par(v)}\\})$.

##### Step (3): Propagation of Component IDs Information.

To compute the $1$-VFT labels, it is required for each vertex $v$ to learn the
component-ID $\mathsf{CID}(u)$ for every light edge $(par(u),u)\in T[s,v]$.
This information is obtained by letting every light vertex $u$ propagate its
$\mathsf{CID}(u)$ over $T_{u}$. Since each vertex $v$ has $O(\log n)$ light
edges on its tree path $T[s,v]$, overall, it is required to receive
$O(\log^{2}n)$ bits of information. This can be done in $\widetilde{O}(D)$
rounds, by a simple pipeline.

##### Step (4): Local Computation of $1$-VFT Labels.

At this point, each vertex $v$ is equipped with all the required information
to locally compute its $1$-VFT label, $\mathsf{L}_{\mathsf{{1F}}}(v)$, as
specified in Sec. 2. By Step (0), $v$ knows its interesting set $I(v)$ (see
Def. 1.1). From Step (2) it holds the component-ID of its heavy child
$\mathsf{CID}(h(v))$; and from Step (3) it holds the component-ID
$\mathsf{CID}(u)$ for every light-edge $(par(u),u)\in T[s,v]$. Since we set
the IDs of components containing $s$ to be $ID(s)$, the received component-IDs
also indicate on the connectivity to $s$ in the corresponding
$G\setminus\\{x\\}$ subgraphs. This completes the description of the
algorithm.

We are now ready to complete the proof of Theorem 1.1 by analyzing the round
complexity of the algorithm, and discussing its centralized implementation.

The round complexity of Steps (0-1) is $\widetilde{O}(D)$ by Lemma B.4 and the
aggregation of $\widetilde{O}(1)$-bit values. Step (3) can be implemented in
$\widetilde{O}(D)$ by a simple pipeline mechanism. As each vertex $v$ collects
the component-ID of $u$ in $G\setminus\\{par(u)\\}$ for every light edge
$(par(u),u)$ in the path $T[s,v]$, it collects $\widetilde{O}(1)$ bits of
information, which can be done in $\widetilde{O}(D)$ rounds.

Our congest algorithm can be simulated in $\widetilde{O}(m)$ time. The
computation of the $n$ sketches $\mathsf{Sketch}_{G}(v)$ for every vertex $v$
takes $\widetilde{O}(m)$ time. The aggregate of sketch information can be then
implemented in $\widetilde{O}(n)$ time. Finally, we claim that the local
computation each vertex $x$ can be done in time $\widetilde{O}(\deg(x))$ where
$\deg(x)$ is the degree of $x$ in $G$. This holds, as in each phase of
Borůvka’s we have $O(\deg(x))$ components, and the computation of each
outgoing edge using the sketch information takes $\widetilde{O}(1)$ time, per
component. Overall, the collection of all $n$ connectivity algorithms in
$G\setminus\\{x\\}$ for every $x\in V$ can be implemented in
$\widetilde{O}(m)$ time. This completes the randomized construction time of
Theorem 1.1.

##  Appendix C Single-Source Dual Failure Connectivity Labels

In this section we provide an independent approach for single-source $2$-VFT
connectivity labels, and prove the following variant of Lemma 1.3:

######  Lemma C.1.

There is a _single-source_ 2-VFT connectivity labeling scheme with label
length $O(\log^{2}n)$ bits. That is, given a query of vertices $\langle
t,x,y\rangle$ along with their labels, one can determine whether the (fixed)
source $s$ and $t$ are $xy$-connected.

##### Heavy Paths.

For this section, will need another concept related to the heavy light
decomposition. Consider the subgraph $T^{\prime}$ of $T$ formed by taking in
all the vertices but only the heavy edges. The connected components of
$T^{\prime}$ are paths (some of length zero, i.e. isolated vertices), each
corresponding to choosing a rooting light vertex in $T$ and going downwards
along the heavy edges until reaching a leaf. Such a path $Q$ is called a
_heavy path_ of $T$. The collection of all heavy paths is denoted by
$\mathcal{Q}$. We give each heavy path $Q\in\mathcal{Q}$ a unique identifier
$\operatorname{ID}(Q)$ of $O(\log n)$ bits (e.g., the ID of its rooting light
vertex). We write $Q_{u}$ to denote the unique heavy path containing vertex
$u\in V$. Occasionally, it will be useful to consider the extension of a heavy
path $Q$ up until the root $s$, denoted $Q^{\uparrow}$. That is,
$Q^{\uparrow}$ is the unique root-to-leaf path in $T$ containing $Q$.
Similarly to Observation 1.1, we have:

######  Observation C.1.

Any root-to-leaf path in $T$ intersects only $O(\log n)$ heavy paths in
$\mathcal{Q}$.

##### Extended IDs Revisited.

We slightly augment our extended vertex IDs presented in Section 1.2, by
including in $\operatorname{EID}(u)$ the number of light vertices in $T[s,u]$,
denoted $\operatorname{nl}(u)$, and the ID of the heavy path containing $u$,
$\operatorname{ID}(Q_{u})$. That is, the extended ID of vertex $u$ is given by

$\operatorname{EID}(u)=\left[\operatorname{ID}(u),\mathsf{ANC}_{T}(u),\operatorname{ID}(h(u)),\mathsf{ANC}_{T}(h(u)),\operatorname{nl}(u),\operatorname{ID}(Q_{u})\right].$

This gives the following:

######  Lemma C.2.

Let $v$ be a vertex. Assume each $w\in I^{\uparrow}(v)$ is associated with a
bit $b(w)\in\\{0,1\\}$ (which may also depend on $v$). For
$k=|I^{\uparrow}(v)|$, let $S$ be the $k$-bit string whose $i^{\text{th}}$ bit
is $b(w)$, where $w$ is the $i^{\text{th}}$ highest vertex in
$I^{\uparrow}(v)$, for all $i$. Then, given the string $S$ and
$\operatorname{EID}(u)$ of any $u\in I^{\uparrow}(v)$, one can report the bit
$b(u)$.

###### Proof.

There are exactly $\operatorname{nl}(u)$ vertices higher than $u$ in
$I^{\uparrow}(v)$, given by $par(w^{\prime})$ for each light $w^{\prime}\in
T[s,u]$. Thus $b(u)$ is the $(\operatorname{nl}(u)+1)^{\text{th}}$ bit of $S$.
∎

##### Single-Source 1-VFT Labels.

In Section 2 we presented $1$-VFT connectivity labels of size $O(\log^{2}n)$.
If we restrict ourselves to _single-source_ , we can modify them to get
$O(\log n)$ size, as follows:

The label of vertex $a$ holds the bitstring composed of
$\mathsf{conn}(s,b^{\prime},G\setminus\\{{b}\\})$ for every $b^{\prime}\in
I(a)$ with $par(b^{\prime})=b$ from highest to lowest, and additionally the
bit $\mathsf{conn}(s,h(a),G\setminus\\{{a}\\})$.

When decoding, given the labels of a target $t$ and a failure $x$, we first
check if $x$ is a heavy or light ancestor of $t$. If it is neither, we
determine that $s,t$ are $x$-connected. If it a heavy ancestor, we report
$\mathsf{conn}(s,h(x),G\setminus\\{{x}\\})$ from the label of $x$. If it is a
light ancestor, we report the $(\operatorname{nl}(x)+1)^{\text{th}}$ bit of
the bitstring part of the label of $t$. (This is essentially using Lemma C.2.)

To summarize, we have:

######  Lemma C.3.

There is a _single-source_ $1$-VFT connectivity labeling scheme with $O(\log
n)$-bit labels $\mathsf{L}_{\mathsf{{SS1F}}}(a)$ for every $a\in V$. That is,
given a query of vertices $\langle t,x\rangle$ along with their
$\mathsf{L}_{\mathsf{{SS1F}}}$ labels, one can determine whether the (fixed)
source $s$ and $t$ are $x$-connected.

##### Preliminary Assumptions.

We assume, w.l.o.g., that the following two conditions hold for the query
$\langle t,x,y\rangle$:

  1. (S1)

$s,t$ are both $x$-connected and $y$-connected.

  2. (S2)

$x\in T[s,t]$ and $y\notin T[x,t]$.

To verify (S1) we use the single-source $1$-VFT labels, which consume only
$O(\log n)$ bits, hence within our budget. If (S1) does not hold, then $s,t$
are clearly $xy$-disconnected and we are done. We enforce condition (S2) using
extended IDs, as follows. If none of the failures $x,y$ lie in $T[s,t]$, then
$s,t$ are $xy$-connected and we are done. Otherwise, by swapping $x$ and $y$
if necessary, we may assume that $x$ is the lowest failure on $T[s,t]$, which
gives (S2). From this point on, let $x^{\prime}$ be the child of $x$ on the
path $T[x,t]$. By (S2) we get that $x^{\prime},t$ are $xy$-connected.
Therefore, in the following it is sufficient for us to determine the
$xy$-connectivity of $s,x^{\prime}$.

Condition (S1) serves to justify the existence of several replacement paths
and important vertices which we define in our labels. However, such explicit
justifications are omitted for clarity of presentation. For the same reason,
we also omit explanations about how to extract specific pieces of information
from a label storing them (e.g. by using Lemma C.2). Throughout, we make
extensive use of the properties of interesting sets from Lemma 1.5.

##### Strategy.

We handle differently four different cases based on the location of $y$. The
first three are cases handling dependent failures, and the last is for
independent failures.101010To distinguish between the cases, we use extended
IDs.

  * •

The Down case: $y\in T_{x^{\prime}}$

  * •

The Up case: $y\in T[s,x)$

  * •

The Side case: $y\in T_{x}\setminus T_{x^{\prime}}$

  * •

The Independent case: $x$ and $y$ are independent.

###  C.1 The Down Case: $y\in T_{x^{\prime}}$

##### Labels for Down Case.

For a vertex $u$, define

$\displaystyle A_{u}$ $\displaystyle=\\{v\in T_{u}\mid\text{$s,v$ are
$(T_{u}^{+}\setminus\\{v\\})$-connected}\\},$ (C.1) $\displaystyle\alpha_{u}$
$\displaystyle=\operatorname{LCA}(A_{u}),$ (C.2) $\displaystyle\beta_{u}$
$\displaystyle=\arg\max_{v}\\{0pt(v)\mid\text{$v\in T[s,par(u))$ and $u,v$ are
$(T[s,par(u)]\setminus\\{v\\}))$-connected}\\}.$ (C.3)

The labels for the Down case constructed by Algorithm 6. Using Lemma 1.5 we
see that $\mathsf{L}_{\mathsf{{D}}}(u)$ has length $O(\log^{2}n)$ bits.

1 for  _each $v^{\prime}\in I(u)$ with $par(v^{\prime})=v$_ do

2 store vertices $v,v^{\prime},\alpha_{v^{\prime}},\beta_{v^{\prime}}$;

3 store the bitstring
$[\mathsf{conn}(s,v^{\prime},G\setminus\\{{v,w}\\}),\text{ $\forall w\in
I^{\uparrow}(\alpha_{v^{\prime}})$ from highest to lowest}]$;

4

Algorithm 6 Construction of label $\mathsf{L}_{\mathsf{{D}}}(u)$ for vertex
$u$

##### Decoding Algorithm for Down Case.

The algorithm proceeds by the following steps.

Step (1): Detecting $\alpha:=\alpha_{x^{\prime}}$. As $x^{\prime}\in I(t)\cup
I(x)$, $\alpha:=\alpha_{x^{\prime}}$ is stored in either
$\mathsf{L}_{\mathsf{{D}}}(t)$ or $\mathsf{L}_{\mathsf{{D}}}(x)$. We treat two
easy cases:

Case 1: $\alpha\notin T_{y}$. As $\alpha=\operatorname{LCA}(A_{x^{\prime}})$,
there must be some $u\in A_{x^{\prime}}\setminus T_{y}$. By Eq. (C.1), $u\in
T_{x^{\prime}}$ and there is an $s$-$u$ path $P$ internally avoiding
$T_{x^{\prime}}^{+}$. Now $P\circ T[u,x^{\prime}]$ certifies that
$s,x^{\prime}$ are $xy$-connected, and we are done.

Case 2: $y\in I^{\uparrow}(\alpha)$. Then
$\mathsf{conn}(s,x^{\prime},G\setminus\\{{x,y}\\})$ is specified along with
$\alpha$, and we are done.

From now on, assume that $\alpha\in T_{y}$ and $y\notin I^{\uparrow}(\alpha)$.
Hence, the child of $y$ on $T[y,\alpha]$ is $h(y)$. It is not hard to see,
using Eqs. (C.1) and (C.2), that $s,h(y)$ are $xy$-connected by a path of the
form $P\circ T[u,h(x)]$ for some $u\in A_{x^{\prime}}$, where $P$ is an
$s$-$u$ path internally avoiding $T_{x^{\prime}}^{+}$.

Step (2): Detecting $\beta:=\beta_{h(y)}$. Observe that $\beta:=\beta_{h(y)}$
in stored in $\mathsf{L}_{\mathsf{{D}}}(y)$ as $h(y)\in I(y)$. There are two
possible cases.

Case 1: $\beta\in T(x,y)$. By Eq. (C.3), there is an $h(y)$-$\beta$ path $P$
internally avoiding $T[s,y]$. Now $P\circ T[\beta,x^{\prime}]$ certifies that
$h(y),x^{\prime}$ are $xy$-connected, hence this is also true for
$s,x^{\prime}$.

Case 2: $\beta\in T[s,x]$. See Illustration in Figure 4.

[scale=0.5]fig_down.pdf

Figure 4:  The final configuration reached in decoding for the Down case. If
this configuration is reached then $s,t$ are $xy$-disconnected.

We prove that $s,x^{\prime}$ are $xy$-disconnected. Assume the contrary, so
$P=P_{s,x^{\prime},\\{x,y\\}}$ exists. Let $\widetilde{\alpha}$ be the first
vertex from $T_{x^{\prime}}$ in $P$. Then $P[s,\widetilde{\alpha}]$ internally
avoids $T_{x^{\prime}}^{+}$, hence, by Eqs. (C.1) and (C.2) for
$A_{x^{\prime}}$ and $\alpha=\alpha_{x^{\prime}}$,

$\widetilde{\alpha}\in A_{x^{\prime}}\subseteq T_{\alpha}\subseteq
T_{h(y)}\subseteq T_{x}.$

Now let $\widetilde{\beta}$ be the first vertex from $T[s,y)$ in
$P[\widetilde{\alpha},x^{\prime}]$.

  * •

Case $\widetilde{\beta}\in T[s,x)$: Then $T[s,\widetilde{\beta}]$ avoids
$x,y$, so as $P$ is a replacement path going through $s$ and
$\widetilde{\beta}$ we obtain

$\widetilde{\alpha}\in P[s,\widetilde{\beta}]=T[s,\widetilde{\beta}]\subseteq
T[s,x),$

which is a contradiction as $\widetilde{\alpha}\in T_{x}$.

  * •

Case $\widetilde{\beta}\in T(x,y)$: Then $T[h(y),\widetilde{\alpha}]\circ
P[\widetilde{\alpha},\widetilde{\beta}]$ is an $h(y)$-$\widetilde{\beta}$ path
internally avoiding $T[s,y]$, which contradicts the definition of
$\beta=\beta_{h(y)}$ in Eq. (C.3) as the lowest vertex having such a path.

This concludes the decoding algorithm.

For the sake of optimizing the label length in the subsequent constructions,
we observe that one can optimize the length of the labels under if an
additional promise is given:

######  Lemma C.4.

There are $O(\log n)$-bit labels $\mathsf{L}_{\mathsf{{D^{\prime}}}}(u)$ for
all vertices $u\in V$ such that given a query of vertices $\langle
t,x,y\rangle$ along with their labels, where it is promised that $t,y\in
T_{h(x)}$ and $y\notin T[h(x),t]$, one can determine the $xy$-connectivity of
$s,t$.

###### Proof.

We simply replace $I(u)$ by $\\{h(u)\\}$ in the definition of
$\mathsf{L}_{\mathsf{{D}}}(u)$ to get $\mathsf{L}_{\mathsf{{D^{\prime}}}}(u)$.
The decoding algorithm is identical to the Down case, only now
$x^{\prime}=h(x)\in I(x)$, which implies that all the required information is
stored in the smaller $\mathsf{L}_{\mathsf{{D^{\prime}}}}$ labels. ∎

###  C.2 The Up Case: $y\in T[s,x)$

##### Labels for Up Case.

For a vertex $u$ with an $s$-$u$ replacement path $P=P_{s,u,par(u)}$, let
$q_{u}\in P$ be the first (closest to $s$) vertex in $T_{u}$.

######  Observation C.2.

$P_{s,u,par(u)}=P^{\prime}\circ T[q_{u},u]$ where $P^{\prime}$ avoids $T_{u}$.

Next, let $Q\in\mathcal{Q}$ be a heavy path such that $u\in Q^{\uparrow}$. We
define:

$\displaystyle a_{u}$ $\displaystyle=\arg\min_{v}\\{0pt(v)\mid v\in
T[s,par(u))\text{ and $\exists$ $s$-$u$ path avoiding $T(v,par(u)]$}\\},$
(C.4) $\displaystyle b_{u,Q}$
$\displaystyle=\arg\min_{v}\\{0pt(v)\mid\text{$v\in Q^{\uparrow}(u,\ell]$ and
$\exists$ $s$-$v$ path internally avoiding $Q^{\uparrow}[u,\ell]$}\\},$ (C.5)
$\displaystyle c_{u}$ $\displaystyle=\arg\max_{v}\\{0pt(v)\mid\text{$v\in
T[s,u)$ and $\exists$ $h(u)$-$v$ path internally avoiding $T[s,u]$}\\}.$ (C.6)

We note that Eq. (C.4) is equivalent to

$\displaystyle a_{u}$ $\displaystyle=\arg\min_{v}\\{0pt(v)\mid v\in
T[s,par(u))\text{ and $\exists$ $v$-$u$ path internally avoiding
$T[s,par(u)]$}\\}.$ (C.7)

The labels for the Up case are constructed by Algorithm 7.

1 for  _each $v^{\prime}\in I(u)$ with $par(v^{\prime})=v$_ do

2 store vertices $v,v^{\prime},a_{v^{\prime}}$ and value
$\mathsf{conn}(s,v^{\prime},G\setminus\\{{v,a_{v^{\prime}}}\\})$;

3 store the bitstring
$[\mathsf{conn}(s,v^{\prime},G\setminus\\{{v,w}\\}),\text{ $\forall w\in
I^{\uparrow}(v^{\prime})$ from highest to lowest}]$;

4

5store vertices $c_{u},q_{h(u)}$;

6 for  _each heavy path $Q\in\mathcal{Q}$ intersecting $T[s,q_{h(u)}]$_ do

7 store $\operatorname{ID}(Q)$, $b_{u,Q}$ and
$\mathsf{conn}(s,h(u),G\setminus\\{{u,b_{u,Q}}\\})$;

8

Algorithm 7 Construction of label $\mathsf{L}_{\mathsf{{U}}}(u)$ for vertex
$u$

Using Lemma 1.5 and Observation C.1 we see that $\mathsf{L}_{\mathsf{{U}}}(u)$
has length $O(\log^{2}n)$ bits.

##### Decoding Algorithm for Up Case.

The algorithm proceeds by the following steps.

Step (0): We first handle an easy case:

Case: $y\in I^{\uparrow}(x)$. Then as $x^{\prime}\in I(t)\cup I(x)$, the value
$\mathsf{conn}(s,x^{\prime},G\setminus\\{{x,y}\\})$ is stored in either
$\mathsf{L}_{\mathsf{{U}}}(t)$ or $\mathsf{L}_{\mathsf{{U}}}(x)$ (to see this,
set $v=x$, $v^{\prime}=x^{\prime}$ and $w=y$), so we are done.

From now on, assume that $y\notin I^{\uparrow}(x)$. Thus, the child of $y$ on
$T[y,x]$ is $h(y)$.

Step (1): Detecting $a:=a_{x^{\prime}}$. As $x^{\prime}\in I(t)\cup I(x)$,
$a:=a_{x^{\prime}}$ is stored in either $\mathsf{L}_{\mathsf{{U}}}(t)$ or
$\mathsf{L}_{\mathsf{{U}}}(x)$. We treat two easy cases:

Case 1: $a\in T[s,y)$. Then by Eq. (C.4), there is an $s$-$x^{\prime}$ path
avoiding $T(a,x]$, and hence avoiding $x,y$. This shows that $s,x^{\prime}$
are $xy$-connected, so we are done.

Case 2: $a=y$. Then $\mathsf{conn}(s,x^{\prime},G\setminus\\{{x,y}\\})$ is
specified along with $a$, and we are done.

From now on, assume that $a\in T(y,x)=Q_{x}^{\uparrow}(y,x)$. By Eq. (C.7),
there is an $a$-$x^{\prime}$ path $P$ internally avoiding $T[s,x]$, and hence
avoiding $x,y$. Thus, $T[h(y),a]\circ P$ shows that $x^{\prime},h(y)$ are
$xy$-connected.

Step (2): Detecting $q:=q_{h(y)}$. Observe that $q:=q_{h(y)}$ is stored in
$\mathsf{L}_{\mathsf{{U}}}(y)$. We treat an easy case:

Case: $x\notin T[s,q]$. By Observation C.2, $P_{s,h(y),y}=P^{\prime}\circ
T[q,h(y)]$ where $P^{\prime}$ avoids $T_{h(y)}$, and hence avoids $x$.
Therefore, $P_{s,h(y),y}$ is $s$-$h(y)$ path that avoids both $x,y$. Thus
$s,h(y)$ are $xy$-connected, hence this is also true for $s,x^{\prime}$, and
we are done.

From now on, assume that $x\in T[s,q]$.

Step (3): Detecting $b:=b_{y,Q_{x}}$. As $x\in T[s,q]$, the heavy path $Q_{x}$
intersects $T[s,q]$, thus $b:=b_{y,Q_{x}}$ is specified in
$\mathsf{L}_{\mathsf{{U}}}(y)$. Denote by $\ell$ the leaf which is the
endpoint of $Q_{x}$. We treat two easy cases:

Case 1: $b\in T(y,x)=Q_{x}^{\uparrow}(y,x)$. By Eq. (C.5), there is an $s$-$b$
path $P$ internally avoiding $Q_{x}^{\uparrow}[y,\ell]$. Then $P\circ
T[b,h(y)]$ certifies that $s,h(y)$ are $xy$-connected, hence this is also true
for $s,x^{\prime}$, and we are done.

Case 2: $b=x$. Then $\mathsf{conn}(s,h(y),G\setminus\\{{x,y}\\})$ is specified
with $b$, so we are done again.

From now on, assume that $b\in Q_{x}^{\uparrow}(x,\ell]=T[h(x),\ell]$.

Step (4): Detecting $c:=c_{x}$. Observe that $c:=c_{x}$ is stored in
$\mathsf{L}_{\mathsf{{U}}}(x)$. There are two possible cases:

Case 1: $c=T(y,x)=Q_{x}^{\uparrow}(y,x)$. By Eq. (C.6), there is an $h(x)$-$c$
path $P$ internally avoiding $T[s,x]$, and hence avoiding $x,y$. By Eq. (C.5),
there is an $s$-$b$ path $P^{\prime}$ internally avoiding
$Q_{x}^{\uparrow}[y,\ell]$, and hence avoiding $x,y$. The concatenation
$P^{\prime}\circ T[b,h(x)]\circ P\circ T[c,h(y)]$ now certifies that $s,h(y)$
are $xy$-connected, hence this is also true for $s,x^{\prime}$, and we are
done.

Case 2: $c\in T[s,y]=Q_{x}^{\uparrow}[s,y]$. See illustration in Figure 5.

[scale=0.5]fig_up.pdf

Figure 5:  The final configuration reached in decoding for the Up case. If
this configuration is reached then $s,t$ are $xy$-disconnected.

We prove that $s,x^{\prime}$ are $xy$-disconnected. Assume the contrary, so
$P=P_{s,x^{\prime},\\{x,y\\}}$ exists. We divide to cases:

  1. (a)

$P$ avoids $T(y,x)=Q_{x}^{\uparrow}(y,x)$: Let $\widetilde{a}$ be the lowest
vertex from $T[s,y)$ appearing in $P$. Then $P$ is an $s$-$x^{\prime}$ path
avoiding $T(\widetilde{a},x]$, and $\widetilde{a}$ is higher than $a$ —
contradicting Eq. (C.4) for $a=a_{x^{\prime}}$.

  2. (b)

$P$ avoids $T(x,\ell]=Q_{x}^{\uparrow}(x,\ell]$: As (a) yields a
contradiction, $P$ must intersect $Q_{x}^{\uparrow}(y,x)$. Let
$\widetilde{b}\in P$ be the first (closest to $s$) vertex in
$Q_{x}^{\uparrow}(y,x)$. Then $P[s,\widetilde{b}]$ is an $s$-$\widetilde{b}$
path internally avoiding $Q_{x}^{\uparrow}[y,\ell]$, and $\widetilde{b}$ is
higher than $b$ — contradicting Eq. (C.5) for $b=b_{y,Q_{x}}$.

  3. (c)

$P$ intersects $T(x,\ell]=Q_{x}^{\uparrow}(x,\ell]$: Again, as (a) yields a
contradiction, $P$ must intersect $Q_{x}^{\uparrow}(y,x)$. Let
$\widetilde{c}\in P$ be the first (closest to $s$) vertex in
$Q_{x}^{\uparrow}(y,x)=T(y,x)$. It cannot be that $P[s,\widetilde{c}]$ avoids
$Q_{x}^{\uparrow}(x,\ell]$, as this yields the same contradictions as (b).
Thus, there is a vertex $u\in Q_{x}^{\uparrow}(x,\ell]=T[h(x),\ell]$ that
precedes $\widetilde{c}$ on $P$. As $P$ is a replacement path for faults $x,y$
and $T[s,y)$ is fault-free, $P$ starts by going down a segment of $T[s,y)$ and
never returns to $T[s,y)$ again. Therefore, the first vertex from $T[s,x]$
that $P[u,\widetilde{c}]$ hits is $\widetilde{c}$. Thus, $T[h(x),u]\circ
P[u,\widetilde{c}]$ is an $h(x)$-$\widetilde{c}$ path internally avoiding
$T[s,x]$. Also, $\widetilde{c}$ is lower than $c$ — contradicting Eq. (C.6)
for $c=c_{x}$.

This concludes the decoding algorithm.

Finally, we observe that if extra properties are promised to hold, one can
optimize the labeling scheme for the Up case as follows:

######  Lemma C.5.

There are $O(\log n)$-bit labels $\mathsf{L}_{\mathsf{{U^{\prime}}}}(u)$ for
all vertices $u\in V$ such that given a query of vertices $\langle
t,x,y\rangle$ along with their labels, where it is promised that $t\in
T_{h(x)}$ and $x\notin T_{h}(y)$, one can determine the $xy$-connectivity of
$s,t$.

###### Proof.

The proof is similar to Lemma C.4. Namely, we replace $I(u)$ by $\\{h(u)\\}$
in the definition of $\mathsf{L}_{\mathsf{{U}}}(u)$ to get
$\mathsf{L}_{\mathsf{{U^{\prime}}}}(u)$, and can still run the decoding
algorithm for the Up case using these labels. ∎

###  C.3 The Side Case: $y\in T_{x}\setminus T_{x^{\prime}}$

##### Labels for Side Case.

For a vertex $u$ with a replacement path $P=P_{s,u,par(u)}$, let $g_{u}\in P$
as the last (closest to $u$) vertex in $T_{h(par(u))}$. In case $P$ does not
intersect $T_{h(par(u))}$, we define $g_{u}=\mathsf{null}$.

######  Observation C.3.

If $g\neq\mathsf{null}$, then $P_{s,u,par(u)}[g_{u},u]$ internally avoids
$T_{h(par(u))}^{+}$.

For a subgraph $G^{\prime}\subseteq G$, denote by
$\mathsf{L}_{\mathsf{{SS1F}}}(u,G^{\prime})$ the single-source $1$-VFT label
of $u$ from Lemma C.3 constructed w.r.t. the graph $G^{\prime}$ with the same
source $s$.

The labels for the Side case are constructed by Algorithm 8.

1 store $\mathsf{L}_{\mathsf{{D^{\prime}}}}(u)$,
$\mathsf{L}_{\mathsf{{U^{\prime}}}}(u)$;

2 for  _each $v^{\prime}\in I(u)$ with $par(v^{\prime})=v$_ do

3 store $\mathsf{L}_{\mathsf{{SS1F}}}(u,G\setminus\\{{v}\\})$,
$\mathsf{L}_{\mathsf{{SS1F}}}(v^{\prime},G\setminus\\{{v}\\})$;

4 store vertex $g_{v^{\prime}}$,
$\mathsf{conn}(s,v^{\prime},G\setminus\\{{v,g_{v^{\prime}}}\\})$,
$\mathsf{L}_{\mathsf{{D^{\prime}}}}(g_{v^{\prime}})$,
$\mathsf{L}_{\mathsf{{U^{\prime}}}}(g_{v^{\prime}})$;

5 store the bitstring
$[\mathsf{conn}(s,g_{v^{\prime}},G\setminus\\{{v,w}\\}),\text{ $\forall w\in
I^{\uparrow}(g_{v^{\prime}})$ from highest to lowest}]$;

6

Algorithm 8 Construction of label $\mathsf{L}_{\mathsf{{S}}}(u)$ for vertex
$u$

Using Lemma 1.5, Lemma C.3, Lemma C.4 and Lemma C.5, we see that
$\mathsf{L}_{\mathsf{{S}}}(u)$ has length $O(\log^{2}n)$ bits.

##### Decoding Algorithm for Side Case.

The algorithm proceeds by the following steps.

Step (0): Let $x^{\prime\prime}$ be this child of $x$ on $T[x,y]$. Then
$x^{\prime\prime}\neq x^{\prime}$. We first handle an easy case:

Case: $x^{\prime\prime}$ is light. Then $x^{\prime\prime}\in I(y)$, hence
$\mathsf{L}_{\mathsf{{SS1F}}}(y,G\setminus\\{{x}\\})$ is stored in
$\mathsf{L}_{\mathsf{{S}}}(y)$. As $x^{\prime}\in I(t)\cup I(x)$,
$\mathsf{L}_{\mathsf{{SS1F}}}(x^{\prime},G\setminus\\{{x}\\})$ is stored in
either $\mathsf{L}_{\mathsf{{S}}}(t)$ or $\mathsf{L}_{\mathsf{{S}}}(x)$. Using
these $\mathsf{L}_{\mathsf{{SS1F}}}$ labels w.r.t. $G\setminus\\{{x}\\}$, we
determine if $s,x^{\prime}$ are connected in
$(G\setminus\\{{x}\\})\setminus\\{y\\}=G\setminus\\{{x,y}\\}$, and we are
done.

From now on assume that $x^{\prime\prime}=h(x)$, namely $y\in T_{h(x)}$.

Step (1): Detecting $g:=g_{x^{\prime}}$. As $x^{\prime}\in I(t)\cup I(x)$,
$g:=g_{x^{\prime}}$ is stored in either $\mathsf{L}_{\mathsf{{S}}}(t)$ or
$\mathsf{L}_{\mathsf{{S}}}(x)$. If $g=\mathsf{null}$ then the replacement path
$P_{s,x^{\prime},x}$ avoids $T_{h(x)}$, and particularly avoids $y$. Thus,
$s,x^{\prime}$ are $xy$-connected and we are done. If $g=y$, then
$\mathsf{conn}(s,x^{\prime},G\setminus\\{{x,y}\\})$ is specified with $g$, so
we are done again.

From now on, assume that $g\in V\setminus\\{y\\}$. It follows from Observation
C.3 that $g,x^{\prime}$ are $xy$-connected. Thus, it suffices to determine the
$xy$-connectivity of $s,g$. Observe that
$\mathsf{L}_{\mathsf{{D^{\prime}}}}(g),\mathsf{L}_{\mathsf{{U^{\prime}}}}(g)$
are specified with $g$. Also,
$\mathsf{L}_{\mathsf{{D^{\prime}}}}(x),\mathsf{L}_{\mathsf{{U^{\prime}}}}(x)$
and
$\mathsf{L}_{\mathsf{{D^{\prime}}}}(y),\mathsf{L}_{\mathsf{{U^{\prime}}}}(y)$
are stored in $\mathsf{L}_{\mathsf{{S}}}(x)$ and
$\mathsf{L}_{\mathsf{{S}}}(y)$ respectively. There are two possible cases (see
illustration in Figure 6):

[scale=0.5]fig_side.pdf

Figure 6:  The two possible final configurations reached in decoding for the
Side case. Vertices $y_{1}$ and $y_{2}$ represent the different options for
the location of the failure $y$.

Case 1: $y\notin T[s,g]$. Then $g,y\in T_{h(x)}$ and $y\notin T[h(x),g]$. Thus
we apply Lemma C.4 with query $\langle g,x,y\rangle$ and the corresponding
$\mathsf{L}_{\mathsf{{D^{\prime}}}}$ labels to determine the $xy$-connectivity
of $s,g$.

Case 2: $y\in T[s,g)$. If $y\in I^{\uparrow}(g)$, then
$\mathsf{conn}(s,g,G\setminus\\{{x,y}\\})$ is specified along with $g$ and we
are done. Otherwise, the child of $y$ on $T[s,g]$ is $h(y)$, namely $g\in
T_{h(y)}$. Recall that $y\in T_{h(x)}$. Thus we apply Lemma C.5 with query
$\langle g,y,x\rangle$ and the corresponding
$\mathsf{L}_{\mathsf{{U^{\prime}}}}$ labels to determine the $xy$-connectivity
of $s,g$.

###  C.4 The Independent Case: $x$ and $y$ are Independent

##### Labels for Independent Case.

Let $u$ be a vertex. We will need the definition of $\ell_{u}$ and Observation
3.1 from Section 3.2. Recall that for the replacement path $P=P_{s,u,par(u)}$,
the vertex $\ell_{u}\in P$ is the last (closest to $u$) vertex in $T\setminus
T_{par(u)}$, and Observation 3.1 states that $P=T[s,\ell_{u}]\circ P^{\prime}$
where $P^{\prime}\subseteq T_{par(u)}$. Next, let $Q\in\mathcal{Q}$ be a heavy
path. We define:

$\displaystyle d_{u,Q}=\arg\max_{v}\\{0pt(v)\mid\text{$v\in Q$ and $\exists$
$s$-$v$ path internally avoiding $\\{u\\}\cup(Q\setminus T[s,u))$}\\}$ (C.8)

The labels for the Independent case are:

1 for  _each $v^{\prime}\in I(u)$ with $par(v^{\prime})=v$_ do

2 store $v,v^{\prime},\ell_{v^{\prime}}$;

3 store the bitstring
$[\mathsf{conn}(s,v^{\prime},G\setminus\\{{v,w}\\}),\text{ $\forall w\in
I^{\uparrow}(\ell_{v^{\prime}})$ from highest to lowest}]$;

4

5for  _each heavy path $Q\in\mathcal{Q}$ intersecting $T[s,\ell_{h(u)}]$_ do

6 store $\operatorname{ID}(Q)$ and $d_{u,Q}$;

7

Algorithm 9 Construction of label $\mathsf{L}_{\mathsf{{IN}}}(u)$ for vertex
$u$

Using Lemma 1.5 and Observation C.1 we see that
$\mathsf{L}_{\mathsf{{IN}}}(u)$ has length $O(\log^{2}n)$ bits.

##### Decoding Algorithm for Independent Case.

The algorithm proceeds by the following steps.

Step (1): Detecting $\ell_{x}$. As $x^{\prime}\in I(t)\cup I(x)$,
$\ell_{x^{\prime}}$ is stored in either $\mathsf{L}_{\mathsf{{IN}}}(t)$ or
$\mathsf{L}_{\mathsf{{IN}}}(x)$. We handle two easy cases:

Case 1: $y\notin T[s,\ell_{x^{\prime}}]$. By Observation 3.1, it holds that
$P_{s,x^{\prime},x}=T[s,\ell_{x^{\prime}}]\circ P^{\prime}$ where
$P^{\prime}\subseteq T_{x}$. Therefore, $P_{s,x^{\prime},x}$ also avoids $y$,
so $s,x^{\prime}$ are $xy$-connected and we are done.

Case 2: $y\in I^{\uparrow}(\ell_{x^{\prime}})$. Then
$\mathsf{conn}(s,x^{\prime},G\setminus\\{{x,y}\\})$ is specified next to
$\ell_{x^{\prime}}$, so we are done.

From now on assume that $y\in T[s,\ell_{x^{\prime}}]$ and $y\notin
I^{\uparrow}(\ell_{x^{\prime}})$. Thus, the child of $y$ on
$T[y,\ell_{x^{\prime}}]$ is $h(y)$. Now $P_{s,x^{\prime},x}[h(y),x^{\prime}]$
shows that $x^{\prime},h(y)$ are $xy$-connected.

Step (2): Detecting $\ell_{h(y)}$ and $\ell_{h(x)}$. As $h(y)\in I(y)$,
$\ell_{h(y)}$ is stored in $\mathsf{L}_{\mathsf{{IN}}}(y)$. The cases where
$x\notin T[s,\ell_{h(y)}]$ and where $x\in I^{\uparrow}(\ell_{h(y)})$ are
treated similarly to the symmetric cases for $\ell_{x^{\prime}}$. Hence, in
these cases we can determine the $xy$-connectivity of $s,h(y)$, and thus also
of $s,x^{\prime}$.

From now on assume that $x\in T[s,\ell_{h(y)}]$ and $x\notin
I^{\uparrow}(\ell_{h(y)})$. Thus, the child of $x$ on $T[x,\ell_{h(y)}]$ is
$h(x)$. Now $P_{s,h(y),y}[h(x),h(y)]$ shows that $h(y),h(x)$ are
$xy$-connected.

In a symmetric manner, we find $\ell_{h(x)}$ in
$\mathsf{L}_{\mathsf{{IN}}}(x)$. We act in a similar fashion as with
$\ell_{h(y)}$. The only case where we do not finish is when $y\in
T[s,\ell_{h(x)}]$ and $y\notin I^{\uparrow}(\ell_{h(x)})$, so from now on we
assume this case holds.

Step (3): Inspecting $Q_{x}$ and $Q_{y}$. Let $b_{x},b_{y}$ be the leaves of
$T$ which are the endpoints of $Q_{x},Q_{y}$ respectively. Every $w\in
Q_{x}[h(x),b_{x}]$ is $xy$-connected to $h(x)$, and every $w\in
Q_{y}[h(y),b_{y}]$ is $xy$-connected to $h(y)$. Recall now that
$x^{\prime},h(x),h(y)$ are all $xy$-connected. Let $B=Q_{x}[h(x),b_{x}]\cup
Q_{y}[h(y),b_{y}]$ (i.e., all vertices below $x,y$ in $Q_{x},Q_{y}$
respectively). Then all vertices in $B$ are $xy$-connected, and our goal
becomes determining whether there exists $w\in B$ that is $xy$-connected to
$s$. Next, let $A=T[s,x]\cup T[s,y]$. We claim that all vertices in $B$ are
not only $xy$-connected, but in fact $A$-connected. Indeed, the path
$P_{s,h(y),y}[h(x),h(y)]$ serves as a bridge avoiding $A$ between the parts
$Q_{x}[h(x),b_{x}]$ and $Q_{y}[h(y),b_{y}]$ of $B$.

Step (4): Detecting $d_{x}:=d_{x,Q_{y}}$ and $d_{y}:=d_{y,Q_{x}}$. As $y\in
T[s,\ell_{h(x)}]$, $Q_{y}$ intersects $T[s,\ell_{h(x)}]$, so
$d_{x}:=d_{x,Q_{y}}$ is stored in $\mathsf{L}_{\mathsf{{IN}}}(x)$. We also
find $d_{y}:=d_{y,Q_{x}}$ symmetrically. There are two possible cases:

Case 1: $d_{x}\in B$ or $d_{y}\in B$. Assume $d_{x}\in B$ (the case $d_{y}\in
B$ is similar). By Eq. (C.8), there exists an $s$-$d_{x}$ path $P$ internally
avoiding $\\{x\\}\cup(Q_{y}\setminus T[s,x))$, hence $P$ avoids $x,y$. Thus,
$s$ and $d_{x}\in B$ are $xy$-connected, so we are done.

Case 2: $d_{x},d_{y}\in A$. See illustration in Figure 7.

[scale=0.5]fig_ind_ss.pdf

Figure 7:  The final configuration reached in decoding for the Independent
case. If this configuration is reached then $s,t$ are $xy$-disconnected.

We prove that all vertices in $B$ are $xy$-disconnected from $s$, which
concludes the algorithm. Assume the contrary, and let $P$ be an $s$-$w$ path
avoiding $x,y$ for some $w\in B$. We may assume that $w$ is the only vertex
from $B$ in $P$ (otherwise, replace $w$ by the first hitting point in $B$, and
trim $P$ to end there). Let $u\in P$ be the last (closest to $w$) vertex from
$A$. Assume $u\in T[s,x)$ (the case $u\in T[s,y)$ is similar). Then
$T[s,u]\circ P[u,w]$ internally avoids $\\{x\\}\cup(Q_{y}\setminus T[s,x))$.
We divide to cases:

  * •

$w\in Q_{y}[h(y),b_{y}]$: Then $w$ is lower than $d_{x}$, contradicting Eq.
(C.8) for $d_{x}=d_{x,Q_{y}}$.

  * •

$w\in Q_{x}[h(x),b_{x}]$: As all vertices in $B$ are $A$-connected and
$h(y)\in B$, there exists a $w$-$h(y)$ path $P^{\prime}$ internally avoiding
$A$. Let $w^{\prime}$ be the first vertex from $Q_{y}$ that $P^{\prime}$ hits.
Then $T[s,u]\circ P[u,w]\circ P^{\prime}[w,w^{\prime}]$ internally avoids
$\\{x\\}\cup(Q_{y}\setminus T[s,x))$. But as $w^{\prime}\in Q_{y}\setminus A$,
it is lower than $d_{x}$, which again contradicts Eq. (C.8) for
$d_{x}=d_{x,Q_{y}}$.

This concludes the decoding label for the Independent case.

Finally, by concatenating the labels $\mathsf{L}_{\mathsf{{D}}}(u)$,
$\mathsf{L}_{\mathsf{{U}}}(u)$, $\mathsf{L}_{\mathsf{{S}}}(u)$ and
$\mathsf{L}_{\mathsf{{IN}}}(u)$ labels for each $u\in V$, we get a labeling
scheme proving Lemma C.1.