# Deterministic Fault-Tolerant Connectivity Labeling Scheme

Taisuke Izumi111Graduate School of Information Science and Technology, Osaka
University, E-mail<EMAIL_ADDRESS>Yuval Emek222Tehcnion, Israel,
E-mail<EMAIL_ADDRESS>Tadashi Wadayama333Graduate School of
Engineering, Nagoya Institute of Technology, E-mail<EMAIL_ADDRESS>Toshimitsu Masuzawa444Graduate School of Information Science and Technology,
Osaka University, E-mail<EMAIL_ADDRESS>
###### Abstract

The _$f$ -fault-tolerant connectivity labeling_ ($f$-FTC labeling) is a scheme
of assigning each vertex and edge with a small-size label such that one can
determine the connectivity of two vertices $s$ and $t$ under the presence of
at most $f$ faulty edges only from the labels of $s$, $t$, and the faulty
edges. This paper presents a new deterministic $f$-FTC labeling scheme
attaining $O(f^{2}\mathrm{polylog}(n))$-bit label size and a polynomial
construction time, which settles the open problem left by Dory and Parter
[21]. The key ingredient of our construction is to develop a deterministic
counterpart of the graph sketch technique by Ahn, Guha, and McGreger [4], via
some natural connection with the theory of error-correcting codes. This
technique removes one major obstacle in de-randomizing the Dory-Parter scheme.
The whole scheme is obtained by combining this technique with a new
deterministic graph sparsification algorithm derived from the seminal
_$\epsilon$ -net_ theory, which is also of independent interest. As
byproducts, our result deduces the first deterministic fault-tolerant
approximate distance labeling scheme with a non-trivial performance guarantee
and an improved deterministic fault-tolerant compact routing. The authors
believe that our new technique is potentially useful in the future exploration
of more efficient FTC labeling schemes and other related applications based on
graph sketches.

##  1 Introduction

###  1.1 Motivation and Background

Most message-passing distributed systems are modeled by graphs. By the nature
of distributed computing, nodes in the network must cooperatively solve a
given task without rich access to the whole topological information. In
addition, the network is typically prone to faults, i.e., some of the vertices
and/or links can be down by faults. Hence the distributed and compact
representation of some property of the network (e.g., connectivity) adapting
to topology modification is potentially useful for applications in distributed
environments. The _$f$ -fault-tolerant connectivity labeling_ ($f$-FTC
labeling) is a scheme of assigning each vertex and edge with a small-size
label. For any two vertices $s$ and $t$, and an edge set $F$ of $|F|\leq f$,
it determines the connectivity of two vertices $s$ and $t$ under the deletion
of edges $F$ only from the labels of $s$, $t$, and the edges in $F$. The
concept of $f$-FTC labeling schemes (precisely, more general _fault-tolerant
distance labeling schemes_ returning the $s$-$t$ distance rather than the
$s$-$t$ connectivity) has been initiated explictly by Courcelle and Twigg
[15], following an earlier work by Feigenbaum, Karger, Mirrokni, and Sami
[23]. The feature of FTC labeling schemes as a distributed data structure
yields efficient structural algorithms for the _forbidden set routing_ which
routes packets avoiding a given set of faulty edges , and for more general
_fault-tolerant compact routing_ [15, 12, 13, 21, 49] where the faulty edge
set is initially unkonwn.

###  1.2 Our Result

While all of early results [1, 2, 6, 15, 16] mainly focus on the construction
of small-sized labels for restricted graph classes, $f$-FTC labeling schemes
for general graphs were recently proposed by Dory and Parter [21]. They
propose two randomized $f$-FTC labeling schemes of $O(f+\log n)$-bit and
$O(\log^{3}n)$-bit label sizes respectively, which guarantee the weaker form
of the correctness that the response to each _single_ query is correct with
high probability. In other words, they guarantee the correctness only for
$1-1/O(\mathrm{poly}(n))$ fraction of all possible $n^{O(f)}$ queries. We
refer to this type of correctness criteria as “whp query support”, in contrast
with the standard criteria of “full query support” ensuring correct answers
for all possible queries with high probability. The authors of [21] also
mention how the presented two schemes are converted to the ones with full
query support, allowing the blow-up of their label sizes into $O(f\log n)$
bits and $O(f\log^{3}n)$ bits respectively (see the footnote 4 of [21]). In
total, the paper [21] presents the four randomized schemes, two of which
attain full query support and the other two attain only whp query support.
They leave as an open problem the polynomial-time _deterministic_ construction
of compact FTC labeling schemes for general graphs. The main contribution of
this paper is to settle this open problem:

###### Theorem 1

There exist two deterministic $f$-FTC labeling schemes for any graph $G$ of
$n$ vertices and $m$ edges which respectively attain the following bounds:

  * •

The label size is $O(\log n)$ bits per vertex, and $O(f^{2}(\log^{2}n)\log\log
n)$ bits per edge. The query processing time is $\tilde{O}(|F|^{4})$, where
$F$ is the set of queried edges satisfying $|F|\leq f$. The construction time
is polynomial of $m$.

  * •

The label size is $O(\log n)$ bits per vertex, and $O(f^{2}\log^{3}n)$ bits
per edge. The query processing time is $\tilde{O}(|F|^{4})$. The construction
time is near linear, i.e., $\tilde{O}(mf^{2})$.

Note that every deterministic scheme inherently achieves full query support.
We emphasize that de-randomizing any of two original schemes of Dory and
Parter is a highly non-trivial challenge. Those schemes are based on the other
labeling schemes representing a sort of cut structures, whose construction
heavily depends on randomness. Our deterministic construction is based on the
second scheme of Dory and Parter [21] utilzing the _graph sketch_ technique by
Ahn, Guha, and McGreger [4] as the key structure. Informally, the graph sketch
is a labeling scheme to edges, admitting the detection of an outgoing edge for
a given vertex set $S\subseteq V_{G}$ from the bitwise XOR of all labels of
the edges incident to vertices in $S$. The technical highlight of our result
is to develop a deterministic counterpart of the graph sketch technique via
some natural connection with the theory of error-correcting codes. This
technique is very simple, and completely removes one of two major obstacles in
de-randomizing the outgoing edge detection by graph sketches. Yet another
obstacle is the sparsification of the input graph. The sketch-based outgoing
edge detection, including ours, works only when the input vertex set $S$ has a
small number of outgoing edges. To handle the case with many outgoing edges,
the original approach prepares a collection of spanning subgraphs, where for
each possible input $S$ with a non-empty outgoing edge set, there exists at
least one subgraph in the collection such that $S$ has exactly one outgoing
edge. The construction of such a collection follows random sampling of edges.
Our second contribution is a novel de-randomization technique for this graph
sparsification process based on the seminal _$\epsilon$ -net_ theory in
computational geometry [33].

In addition to the key technical ideas above, the construction in Theorem 1
are developed on the top of a few more notable features: First, our result is
presented as a general framework with good modularity, and thus one can easily
transform our deterministic scheme into an efficient randomized FTC labeling
scheme with full query support, just by replacing the graph sparsification
part with the conventional random edge sampling. The construction time and
label size of this randomized scheme are competitive with the original sketch-
based scheme in [21]. Second, we propose a new query optimization strategy. A
drawback of our deterministic outgoing edge detection technique requires the
decoding time roughly quadratic of the label size. Since the sketch-based
$f$-FTC labeling scheme requires $|F|$ iterations of the outgoing edge
detection for processing a single query, the straightforward implementations
result in the $\tilde{O}(f^{4}|F|)$ time for the deterministic case, and
$\tilde{O}(f^{2}|F|)$ time for the randomized case. Our query processing
algorithm shaves off this additional $|F|$ factor, as well as getting rid of
the dependency on $f$ in the outgoing edge detection. Consequently, we obtain
a slightly improved randomized $f$-FTC labeling scheme of $\tilde{O}(|F|^{2})$
decoding time. While the improvement of replacing $f$ by $|F|$ is very
straightforward and easily applicable to any scheme not limited to ours, it is
practically an intriguing feature because in typical scenarios the actual
number of faults $|F|$ is substantially smaller than the upper bound $f$.

The detailed comparison between the schemes in [21] and our schemes are
summarized in Table 1.

###  1.3 Applications

Our deterministic replacement of graph sketches provides a clearer insight to
known outgoing edge detection techniques. It is simple, versatile, and
potentially useful in the future exploration of other applications not limited
to FTC-labeling schemes (e.g., [3, 24, 26, 25, 27, 32, 34, 38, 40, 36, 37,
43]). Actually, we obtain several non-trivial de-randomization results in
related topics. It has been shown in [21] that one can deduce the approximate
distance labeling scheme, which provides an approximate $s$-$t$ distance in
$G-F$ given the labels of $s$, $t$ and the edges in $F$, utilizing any $f$-FTC
labeling scheme in the black-box manner. In addition, such an approximate
distance labeling scheme further deduces an efficient fault-tolerant compact
routing scheme. Since the deduction parts are deterministically implemented,
our deterministic $f$-FTC labeling schemes also de-randomize the construction
of the schemes above. More precisely, we obtain the following applications as
corollaries of Theorem 1.

###### Corollary 1

Assume that the input graph is any weighted undirected graph with polynomially
bounded edge weights. For any positive intergers $k>0$ and $f>0$, there exists
a $f$-fault tolerant $O(|F|k)$-approximate distance labeling scheme which
achieves $\tilde{O}(f^{2}n^{1/k})$-bit label size and $\tilde{O}(|F|^{4})$
query time.

###### Corollary 2

For any positive integer $k>0$ and $f>0$, there exist two deterministic fault-
tolerant compact routing schemes which achieve the stretch factor of
$O(|F|^{2}k)$ and one of the following table-size bounds:

  * •

$\tilde{O}(f^{2}n^{1+1/k})$-bit total table size and
$\tilde{O}(f^{2}n^{1+1/k})$-bit maximum local table size.

  * •

$\tilde{O}(f^{5}n^{1/k})$-bit maximum local table size.

The result of Corollary 1 is the first deterministic scheme for general graphs
achieving a non-trivial performance guarantee. On Corollary 2, the prior work
by Chechik [12], which attains $O(|F|^{2}(|F|+\log^{2}n)k)$ stretch factor
with a smaller table size, is also implemented deterministically, and thus our
result is not the first deterministic solution. However, our scheme takes an
advantage with respect to stretch factors. Since the proofs completely follow
the reduction techniques proposed in [21], this paper does not present the
precise formalism on these corollaries. See [21] for details.

Table 1: Comparison between the schemes in [21] and our results. The dagger mark ${\dagger}$ implies that the complexity is not explicitly stated in the original paper, and thus based on our analyses. For any scheme, the dependency on $f$ in query processing time is easily replaced by $|F|$ utilizing the technique proposed in this paper. | label size | query time | Det./Rand. | correctness | construction
---|---|---|---|---|---
1st (whp) [21] | $O(f+\log n)$ | $\tilde{O}(f^{3})$ | Rand. | whp | $\tilde{O}(fm)$
2nd (whp) [21] | $O(\log^{3}n)$ | $\tilde{O}(|F|)$ | Rand. | whp | $\tilde{O}(fm)$
1st (full)[21] | $O(f\log n)$ | $\tilde{O}(f^{3})^{{\dagger}}$ | Rand. | full | $\tilde{O}(fm)$
2nd (full)[21] | $O(f\log^{3}n)$ | $\tilde{O}(f|F|)^{{\dagger}}$ | Rand. | full | $\tilde{O}(fm)$
This paper | $O(f^{2}\log^{3}n)$ | $\tilde{O}(|F|^{4})$ | Det. | full | $\tilde{O}(fm)$
This paper | $O(f^{2}\log^{2}n\log\log n)$ | $\tilde{O}(|F|^{4})$ | Det. | full | $\mathrm{poly}(n)$
This paper | $O(f\log^{3}n)$ | $\tilde{O}(|F|^{2})$ | Rand. | full | $\tilde{O}(fm)$

###  1.4 Related Work

As mentioned in Section 1.1, FTC-labeling schemes, and more general fault-
tolerant (approximate) distance labeling schemes are introduced in the
literature of _forbidden set routing_ , which is the routing scheme avoiding
non-adaptive faulty edges/vertices (i.e., the set of faults is not specified
at the construction of routing tables, but given at the beginning of packet
routing). The first result by Courcelle and Twigg [15] presents a FTC-labeling
scheme of $O(k^{2}\log n)$-bit labels for graphs of treewidth $k$, as well as
its application to forbidden-set routing. A few results following this line
exist [1, 2, 6, 15, 16], but all of them are interested in the construction of
compact labels for specific graph classes. The result for general graphs is
not much addressed until the result by Dory and Parter [21]. In the context of
deterministic construction, many of the results for restricted graphs stated
above are deterministic, but the deterministic construction for general graphs
is not known so far. In the paper of Dory and Parter, two randomized FTC
labeling schemes relying on different techniques are presented. While the
second scheme is based on graph sketches as we mentioned, the first one relies
on the cut-verification labeling by Pritchard and Thurimella [48].

There are many works in the literature of the centralized version of
connectivity oracles and (approximate) distance oracles supporting edge/vertex
deletion [7, 5, 8, 13, 10, 22, 18, 19, 20, 28, 29]. One of the major setting
on this line is the case of $f=1$, which is known as the _replacement path
problem_ [29, 28, 8], or _distance sensitivity oracle_ [22, 8, 7, 5]. Roughly,
the replacement path problem computes all pair (approximate) shortest path
distances for every possible single edge/vertex fault. The sensitivity oracle
is further required to store the information of replacement paths into a
compact data structure. Their single-source variants are also investigated [7,
9]. The sensitivity oracles for multiple faults are considered mainly in the
context of _fault-tolerant compact routing_ , which is a generalization of
forbidden-set routing addressing adaptive faults (i.e., the set of faults is
not explicitly given at the beginning of packet routing) [12, 13, 21, 49].
There are also a few results considering the oracles specific to connectivity
[47, 18, 19, 20], which are seen as centralized counterparts of FTC labeling
schemes. Obviously, any $f$-FTC labeling scheme is also usable as a
centralized oracle with the space complexity of $m$ times of label size. More
general _dynamic connectivity_ of undirected graphs aims to develop the data
structure of supporting the operations of inserting/deleting edges as well as
the connectivity query. By definition, such a data structure can be used as a
fault-tolerant connectivity oracle with the query processing time of
$O(|F|\cdot\text{(operation cost)})$. While there is a long history of this
problem [50, 30, 31, 11, 51, 44, 36, 25], all the known results with
$\mathrm{polylog}(n)$-time operation cost rely on amortized analyses or the
correctness criteria of whp guarantee. Focusing on deterministic construction,
the best known results are the algorithm by Chuzhoy, Gao, Li, Nanongkai, Peng
and Saranurak for dynamic connectivity achieving $n^{o(1)}$ operation cost per
one edge deletion [11], and the connectivity oracle by Pătraşcu and Throup
[47] achieving $\tilde{O}(|F|)$ query processing time. The deterministic
algorithm for dynamic connectivity with worst-case $\mathrm{polylog}(n)$-time
operation is a major open problem in this research field.

While this paper focuses only on edge faults, it is also an interesting
research direction to consider vertex faults. Despite its similarity, vertex
fault-tolerance often exhibits a technical difficulty quite different from
edge fault-tolerance. A trivial approach is to reduce the failure of a vertex
$v$ into the failure of all the edges incident to $v$, which results in a
$f$-vertex fault tolerant connectivity labeling scheme of $\tilde{O}(\Delta
f)$-bit label size (where $\Delta$ is the maximum degree of the input graph).
Unfortunately, this approach does not provide a good worst-case bound because
$\Delta$ could become $\Omega(n)$. Recently, vertex fault tolerant labeling
schemes for small $f$ are proposed by Parter and Petruschka [46]. They provide
two schemes respectively attaining a polylogarithmic label size for $f=2$ and
a sublinear size for $f=o(\log\log n)$.

The graph sketch technique is first presented by Ahn, Guha, and McGreger [4],
aiming to develop space-efficient algorithms for graph stream [3, 40, 38].
There are a variety of applications not limited to graph stream, such as
distributed computation [24, 26, 27, 32, 34, 37, 43] and dynamic algorithms
[25, 36].

###  1.5 Roadmap

Following the introduction of necessary notations and definitions, we first
explain the high-level idea of our framework in Section 3, including the
explanation of the sub-components constituting our scheme. Section 4 explains
the key technical ideas of our de-randomization technique. Following the
summary of whole structure in Section 5, we present a further query
optimization technique in Section 6. Finally, we conclude this paper in
Section 7, as well as a few promising future research directions.

##  2 Notations and Terminologies

We denote the vertex set and edge set of a graph $G$ respectively by $V_{G}$
and $E_{G}$. We use the notation $H\subseteq G$ to represent that $H$ is a
subgraph of $G$. For any edge subset $E^{\prime}\subseteq E_{G}$, we define
$G-E^{\prime}$ as the graph obtained from $G$ by removing all the edges in
$E^{\prime}$. Given a vertex subset $S\subseteq V_{G}$, an _outgoing edge_ of
$S$ is the edge having exactly one endpoint in $S$. We define
$\partial_{G}(S)$ as the set of all outgoing edges of $S$ in $G$. For any
$E^{\prime}\subseteq E_{G}$, we also define
$\partial_{E^{\prime}}(S)=\partial_{G}(S)\cap E^{\prime}$.

Given a rooted tree $T$ and vertex $v\in V_{T}$, we denote by $T(v)$ the
subtree of $T$ rooted by $v$. Given an edge $e\in E_{T}$, we also denote by
$T(e)$ the subtree of $T$ rooted by the lower vertex (i.e., the endpoint
farther from the root than the other) of $e$.

An _$f$ -FTC labeling scheme_ for a given input graph $G$ consists of a
labeling function $L^{\mathsf{con}}_{G,f}$ and a universal decoding function
$D^{\mathsf{con}}_{f}$. The labeling function assigns each of vertices and
edges $x\in V_{G}\cup E_{G}$ with a label $L^{\mathsf{con}}_{G,f}(x)$ (i.e., a
binary string). Let $s,t\in V_{G}$ be any two vertices and $F\subseteq E$ be
any edge subset of size at most $f$. The decoder function
$D^{\mathsf{con}}_{f}$ correctly answers the connectivity between $s$ and $t$
in $G-F$ only with the information of $L^{\mathsf{con}}_{G,f}(s)$,
$L^{\mathsf{con}}_{G,f}(t)$, and $\\{L^{\mathsf{con}}_{G,f}(e)\mid e\in F\\}$.
Note that the decoder function $D^{\mathsf{con}}_{f}$ is universal for all
$G$, and cannot have any direct access to the information of $G$. The detailed
formalism of $f$-FTC labeling scheme is given in Appendix A.

##  3 Construction Framework

We first introduce a general framework of constructing the $f$-FTC labeling
scheme. The technical core of this framework relies on the scheme by Dory and
Parter [21], but some additional techniques and abstractions are newly
introduced. Let $G$ be the undirected input graph of $n$ vertices and $m$
edges. Throughout this paper, we fix an arbitrary rooted spanning tree $T$ of
$G$. The framework consists of two technical components. The first one is a
weaker variant of $f$-FTC labeling schemes which supports only the query
$(s,t,F)$ satisfying $F\subseteq E_{T}$ (i.e., only the edges in $T$ can be
faulty). We refer to this scheme as the _tree edge $f$-FTC labeling scheme_.
Our tree edge $f$-FTC labeling scheme is implemented with two other labeling
schemes, respectively referred to as the _ancestry labeling scheme_ and the
_$\mathcal{S}$ -outdetect labeling scheme_ (explained in the next section).
The second component is the very simple transformer which deduces an $f$-FTC
labeling scheme from any tree edge $f$-FTC labeling scheme with no blow up of
label size. In the following sections we explain the outline of each
component.

###  3.1 Tree Edge $f$-FTC Labeling Scheme

First, we state the informal specifications of the two sub-schemes. The formal
definitions of these sub-schemes are also presented in Section A.

  * •

Ancestry Labeling Scheme: Let $T$ be any tree. This scheme assigns each vertex
$v\in V_{T}$ with a label $L^{\mathsf{anc}}_{T}(v)$. Given two labels
$L^{\mathsf{anc}}_{T}(u)$ and $L^{\mathsf{anc}}_{T}(v)$ of distinct vertices
$u,v\in V_{T}$, one can determine if $u$ is the ancestor of $v$, the
descendant of $v$, or otherwise. There exists a linear-time deterministic
algorithm which provides the ancestry labeling of $O(\log n)$ bits [39].

  * •

$\mathcal{S}$-Outdetect Labeling Scheme: We assume that each edge $e\in E_{G}$
is assigned with a unique ID from some domain $\mathcal{E}$. Let
$\mathcal{S}\subseteq 2^{V_{G}}$ be a collection of vertex subsets. An
$\mathcal{S}$-outdetect labeling scheme assigns each vertex $v\in V_{G}$ with
a label $L^{\mathsf{out}}_{G}(v)$. For any vertex subset $S\in\mathcal{S}$
such that $\partial_{G}(S)$ is nonempty, one can compute an outgoing edge
$e\in\partial_{G}(S)$ only from the bitwise XOR sum $\bigoplus_{v\in
S}L^{\mathsf{out}}_{G}(v)$ of all the labels assigned to vertices in $S$. If
$\partial_{G}(S)$ is empty, the scheme also detects it. The _graph sketch_
technique [1] provides a randomized $\mathcal{S}$-outdetect labeling scheme
with $O((\log|\mathcal{S}|)\cdot\mathrm{polylog}(n))$-bit label size.

We define $\mathcal{S}_{f,T}$ as the collection of all vertex subsets $S$
satisfying $\partial_{T}(S)\leq f$. Note that $S$ is not required to induce a
connected subtree of $T$. Roughly, our tree edge $f$-FTC labeling scheme is
the combination of the ancestry labeling scheme of $T$ and the
$\mathcal{S}_{f,T}$-outdetect labeling scheme of $G-E_{T}$ for an appropriate
edge ID domain $\mathcal{E}$ (explained later). Each vertex $u$ is assigned
with the ancestry label of $u$, and each tree edge $e=(u,v)$ in $E_{T}$ is
assigned with the concatenation of the ancestry labels of $u$ and $v$, and the
XOR sum of the $\mathcal{S}_{f,T}$-outdetect labels over all the descendant
vertices of $e$. We do not have to assign any label to non-tree edges because
we focus on the construction of the tree edge $f$-FTC labeling scheme.

Given a query $(s,t,F)$ satisfying $F\subseteq E_{T}$ and $|F|\leq f$, the
spanning tree $T$ is split into $|F|+1$ subtrees by removing all the edges in
$F$. We refer to the vertex set of each split subtree as a _fragment_. Let $S$
be the fragment of containing $s$. The query processing algorithm iteratively
grows $S$ by detecting an outgoing edge $e\in\partial_{G-E_{T}}(S)$. If such
an edge is found, the fragment that $e$ reaches from $S$ is merged into $S$.
This process terminates until no outgoing edge is found or the fragment with
$t$ is merged. If no outgoing edge is found, one can conclude that $s$ and $t$
are not connected in $G-F$, or connected otherwise. Our framework detects an
outgoing edge of $S$ in $G-E_{T}$ by the $\mathcal{S}_{f,T}$-outdetect
labeling scheme (recall $S\in\mathcal{S}_{f,t}$ by definition). With the
support of the ancestry labeling scheme, one can detect the ancestor-
descendant relationship between any entities in $s$, $t$, and $F$, which
provides the information of the edge set $\partial_{T}(S^{\prime})$ for all
fragments $S^{\prime}$. To compute $\bigoplus_{v\in
S^{\prime}}L^{\mathsf{out}}_{G-E_{T}}(v)$ for each fragment $S^{\prime}$, it
suffices to compute the XOR sum of the $\mathcal{S}_{f,T}$-outdetect labels
assigned to the edges in $\partial_{T}(S^{\prime})$. Since the outdetect label
of each edge in $T$ is the XOR sum of all descendants’ outdetect labels, it
appropriately cancels out the labels assigned with the vertices not in
$S^{\prime}$. The fragment merging is simple but has a point to be careful.
Let $e=(u,v)$ be an outgoing edge of $S$ (assuming $u\in S$), and $S^{\prime}$
be the fragment containing $v$. Then the XOR sum over all the labels of $S\cup
S^{\prime}$ is easily calculated by the XOR sum of the two computed sums for
$S$ and $S^{\prime}$. However, how can we identify the fragment $S^{\prime}$
containing $v$? This problem is resolved by embedding the ancestry labels of
$u$ and $v$ into the edge ID of $e$. That is, as a preprocessing step, we
assign each edge $(u,v)$ with the pair of
$(L^{\mathsf{anc}}_{T}(u),L^{\mathsf{anc}}_{T}(v))$ as the edge ID, and the
outdetect labeling is constructed for the edge domain by this assignment. Then
the decoding of an edge ID immediately yields the information of the fragments
containing its endpoints. We formalize our framework explained above into the
following lemma.

###### Lemma 1

Assume any deterministic $\mathcal{S}_{f,T}$-outdetect labeling scheme
$(L^{\mathsf{out}}_{G},D^{\mathsf{out}})$ of label size $\alpha$ and decoding
time $\beta$. Then there exists a deterministic tree edge $f$-FTC labeling
scheme of $(\alpha+O(\log n))$-bit label size and $O(|F|(\beta+\log|F|))$
decoding time, where $F$ is a set of faulty edges given by a query.

The proof details are given in Appendix B.1.

###  3.2 Transformation to General Scheme

The second component reduces the construction of general $f$-FTC labeling
schemes into that of tree edge $f$-FTC labeling schemes. For the input graph
$G$ and its rooted spanning tree $T$, our transformation constructs an
auxiliary graph $G^{\prime}$ by subdividing all non-tree edges $e\in
E_{G}\setminus E_{T}$ into two edges, respectively referred to $e$, and
$e^{\prime}$ (see Figure 1). The spanning tree $T^{\prime}$ of $G^{\prime}$ is
also obtained by adding $e$ to the tree $T$. This input transformation
naturally defines an injective (but not onto) mapping $\sigma:E_{G}\to
E_{T^{\prime}}$, where every edge $e\in E_{G}$ is mapped to the corresponding
edge in $T^{\prime}$ with the same name. A query $(s,t,F)$ for $G$ is also
naturally interpreted to the query $(s,t,\\{\sigma(e)|e\in F\\})$ for
$G^{\prime}$. It is easy to see that $s$ and $t$ are connected in $G-F$ if and
only if they are connected in $G^{\prime}-\\{\sigma(e)|e\in F\\}$. Hence the
following proposition obviously holds:

###### Proposition 1

Let $G$ and $T$ be the input graph and its rooted spanning tree, and
$G^{\prime}$, $T^{\prime}$, and $\sigma$ be the graphs and the mapping as
defined above. Assume any tree edge $f$-FTC labeling scheme
$(L^{\mathsf{tree}}_{G^{\prime},f},D^{\mathsf{tree}}_{f})$ for $G^{\prime}$
and $T^{\prime}$. Then we define the labeling function
$L^{\mathsf{con}}_{G,f}$ for $G$ as follows:

$\displaystyle
L^{\mathsf{con}}_{G,f}(x)=\begin{cases}L^{\mathsf{tree}}_{G^{\prime},f}(x)&\text{if
$x\in V_{G}\cup E_{T}$}\\\
L^{\mathsf{tree}}_{G^{\prime},f}(\sigma(x))&otherwise.\end{cases}.$

Then $(L^{\mathsf{con}}_{G,f},D^{\mathsf{tree}}_{f})$ is a $f$-FTC labeling
scheme for $G$.

Figure 1: Auxiliary graph $G^{\prime}$

Combining Lemma 1 and Proposition 1, we obtain the following corollary:

###### Corollary 3

Assume any deterministic $\mathcal{S}_{f,T}$-outdetect labeling scheme
$(L^{\mathsf{out}}_{G},D^{\mathsf{out}})$ of label size $\alpha$ whose
decoding time is $\beta$. Then there exists a deterministic $f$-FTC labeling
scheme of $(\alpha+O(\log n))$-bit label size and $O(|F|(\beta+\log|F|)$
decoding time, where $F$ is a set of faulty edges given by a query.

##  4 Technical Outline of Our Approach

###  4.1 Obstacles in De-Randomization

Corollary 3 implies that the difficulty of de-randomization lies only at the
implementation of the deterministic $\mathcal{S}_{f,T}$-outdetect labeling
scheme. The known $\mathcal{S}$-outdetect labeling scheme based on the graph
sketch includes two major points reling on random bits, which are summarized
as follows:

  * •

The first is at the computation of vertex labels. Let $I_{G}(v)$ be the set of
incident edges of $v$ in $G$. The graph sketch first prepares some function
$g:\mathcal{E}\to\\{0,1\\}^{k}$, where $\mathcal{E}$ is the edge ID domain and
$k$ is the label length, and define the label $L^{\mathsf{out}}_{G}(v)$ of
vertex $v$ as the bitwise XOR sum of $g(e)$ for all the edges $e\in I_{G}(v)$.
When computing $\bigoplus_{v\in S}L^{\mathsf{out}}_{G}(v)$ for a given subset
$S\subseteq V_{G}$, the value $g(e)$ for any $e$ lying at the inside of $S$
are canceled out because the term $g(e)$ appears exactly twice in the sum
$\bigoplus_{v\in S}L^{\mathsf{out}}_{G}(v)=\bigoplus_{v\in S}(\bigoplus_{e\in
I_{G}(v)}g(e))$. That is, $\bigoplus_{v\in
S}L^{\mathsf{out}}_{G}(v)=\bigoplus_{e\in\partial_{G}(S)}g(e)$ holds. For
clarifying the essence of the first point, we consider the simple case such
that $|\partial_{G}(S)|=1$ holds (the general case is addressed in the second
point). In this case, $\bigoplus_{v\in S}L^{\mathsf{out}}_{G}(v)=g(e)$
obviously holds for the unique outgoing edge $e$ of $S$. Hence one can extract
the outgoing edge ID from $\bigoplus_{v\in S}L^{\mathsf{out}}_{G}(v)$,
provided that there exists a way of computing the inverse $g^{-1}$. However,
if $g$ is not well-designed, some subset $S^{\prime}\in\mathcal{S}_{f,T}$
which does not have $e$ as an outgoing edge might accidentally satisfy
$\bigoplus_{v\in S^{\prime}}L^{\mathsf{out}}_{G}(v)=g(e)$. Then, $e$ is
wrongly detected as an outgoing edge of $S^{\prime}$. To avoid it, the graph
sketch needs to guarantee that $\bigoplus_{v\in
S^{\prime}}L^{\mathsf{out}}_{G}(v)$ becomes different from the value $g(e)$ of
any edge $e\in E_{G}$ if $|\partial_{G}(S^{\prime})|\neq 1$. The first point
of utilizing random bits is to attain this condition by taking a random hash
function $g$.

  * •

As explained above, the graph sketch provides the $\mathcal{S}$-outdetect
labeling scheme working only for $S\in\mathcal{S}$ satisfying
$|\partial_{G}(S)|=1$. To cover the case of $\partial_{G}(S)>1$, the original
scheme prepares the collection $\mathcal{G}$ of spanning subgraphs of $G$ such
that for any $S\in\mathcal{S}$ there exists a corresponding $H\in\mathcal{G}$
which satisfies $\partial_{H}(S)=1$. The label to vertex $v$ is then obtained
by the concatenation of $L^{\mathsf{out}}_{H}(v)$ for all $H\in\mathcal{G}$.
Roughly, each spanning subgraph in $\mathcal{G}$ must be (almost everywhere)
sparser than the original input $G$. The construction of each graph in that
collection follows a stochastic sampling of edges, which is the second point
relying on randomization.

The technical highlight of our deterministic scheme is twofold, which
respectively resolve the two issues above. We explain the outline of each
technique in the remainder of this section. The formal argument is provided in
Appendix B.2.

###  4.2 First Technique: Deterministic $k$-Threshold Outdetect Labeling
Scheme

The first technique is a deterministic function $g$ replacing the random
function of the graph sketch, based on the theory of error-correcting codes.
To explain it, we first present a very concise review of coding theory: A
_linear code_ $W$ is a $y$-dimensional linear subspace of
$\mathrm{GF}(2)^{x}$, where $\mathrm{GF}(2)$ is the finite field of two
elements (i.e., the element set $\\{0,1\\}$ and every calculation is done in
modulo 2), $y$ is the length of source data, and $x$ is the length of
codewords. We abuse $W$ as the set of all codewords. The _minimum distance_ of
a linear code is the minimum Hamming distance over all pairs of the codewords
in $W$. In principle, any linear code with minimum distance $k$ can correct
any error of less than $k/2$ symbols (but it does not necessarily imply that
there exists an efficient algorithm of correcting errors). One of the standard
approaches of correcting errors is the _syndrome decoding_ based on _parity
check matrices_. The parity check matrix $C$ of $W$ is the full-rank
$x\times(x-y)$ matrix satisfying $w\cdot C=0$ for any codeword $w\in W$. Since
the parity check matrix of $W$ is uniquely determined from $W$, linear codes
are often defined by the corresponding parity check matrices. A key property
of the parity check matrix is that given a codeword with noise $w+\delta$,
where $w\in W(A)$ and $\delta$ is a noise vector, $(w+\delta)\cdot
C=\delta\cdot C$ holds. The _syndrome_ of a received (noisy) codeword
$w+\delta$ is the vector $(w+\delta)\cdot C$, and the syndrome decoding is the
process of recovering $\delta$ from the syndrome $(w+\delta)\cdot
C=\delta\cdot C$. If $\delta$ is correctly recovered, the noiseless codeword
$w$ is also recovered by adding $\delta$ to the received codeword $w+\delta$.

The background idea of our first technique is as follows: We treat
$g:\mathcal{E}\to\\{0,1\\}^{\ell}$ as the mapping from $\mathcal{E}$ to
$\ell$-dimensional row vectors over $\mathrm{GF}(2)$ (where $\ell$ is the
label size), and define the $|\mathcal{E}|\times\ell$ matrix
$C=(c_{e,i})_{e\in\mathcal{E},i\in[0,\ell-1]}$, where $c_{e,i}$ is the $i$-th
bit of $g(e)$. Let $w(X)=(w_{e})_{e\in\mathcal{E}}$ be the characteristic row
vector for $X\subseteq\mathcal{E}$, i.e., $w_{e}=1$ if $e\in X$, or zero
otherwise. Then the following equality holds for any $S\subseteq V$:

$\displaystyle w(\partial_{G}(S))\cdot
C=\sum_{e\in\partial_{G}(S)}g(e)=\sum_{v\in S}L^{\mathsf{out}}_{G}(v).$

Note that the summation $\sum$ is the sum over $\mathrm{GF}(2)$, and thus that
operation is equivalent to the bitwise XOR. What we need is the recovery of
one non-zero entry in $w(\partial_{G}(S))$ from the right-side sum. This task
can be interpreted into the following scenario: Consider the linear code whose
parity check matrix is $C$. Then recover the noise vector $w(\partial_{G}(S))$
from the syndrome $w(\partial_{G}(S))C=\sum_{v\in S}L^{\mathsf{out}}_{G}(v)$.
If the linear code defined by $C$ has a minimum distance $k>0$, one can obtain
the complete recovery of $w(\partial_{G}(S))$ for any $S$ satisfying
$|\partial_{G}(S)|<k/2$. Since fixing $C$ implies fixing $g$ (and thus the
labeling function $L^{\mathsf{out}}_{G}$), one can obtain the deterministic
function $g$ from the parity check matrix of any linear code. We show that
_Reed-Solomon code_ nicely fits our objective555Precisely, Reed-Solomon code
is a non-binary code. Hence we need to generalize the argument above slightly,
from $\mathrm{GF}(2)$ to any general finite field of characteristic two. The
detailed formalism is given in Appendix A., which provides the outdetect
labeling of $O(k\log n)$ bits supporting the detection of _all_ outgoing edges
of a given subset $S\in 2^{V_{G}}$ in $O(k^{2})$ time if
$|\partial_{G}(S)|\leq k$ holds. We refer to such a scheme as the _$k$
-threshold outdetect labeling scheme_ hereafter. Let
$(L^{\mathsf{RS}(k)}_{H},D^{\mathsf{RS}(k)})$ be the $k$-threshold outdetect
labeling scheme for $H\subseteq G$ defined by the $|\mathcal{E}|\times 2k$
parity check matrix of Reed-Solomon code. It satisfies the following
properties:

###### Proposition 2

The $k$-threshold outdetect labeling scheme
$(L^{\mathsf{RS}(k)}_{H},D^{\mathsf{RS}(k)})$ satisfies the following
conditions:

  * •

The label size is $O(k\log n)$ bits.

  * •

The time taken to assign the labels $L^{\mathsf{RS}(k)}_{H}(v)$ to all
vertices $v\in V_{H}$ is $O(mk)$. The time of computing
$D^{\mathsf{RS}(k)}(L^{\mathsf{RS}(k)}_{H}(S))$ for given
$L^{\mathsf{RS}(k)}_{H}(S)$ is always bounded by $O(k^{2})$.

  * •

Given $L^{\mathsf{RS}(k)}_{H}(S)$, the output of the decoding function is the
IDs of all edges in $\partial_{H}(S)$ if $|\partial_{H}(S)|\leq k$ holds. If
$|\partial_{H}(S)|>k$, the returned value is unspecified. That is, an
arbitrary value can be returned.

In contrast with the single edge detection capability of the original graph
sketch, it is a great advantage that our technique admits the detection of at
most $k$ outgoing edges, which made the construction of the collection
$\mathcal{G}$ much easier. It suffices to construct the sparsification
hierarchy $E_{G-E_{T}}=E_{0}\supseteq E_{1}\supseteq
E_{2}\supseteq,\dots,\supseteq E_{h}=\emptyset$ for $h=O(\log n)$ such that
every $S\in\mathcal{S}_{f,T}$ satisfying $\partial_{G}(S)\neq\emptyset$ admits
a graph $G_{i}=(V,E_{i})$ satisfying $0<|\partial_{G_{i}}(S)|\leq k$. We
define such a hierarchy as a _$(\mathcal{S},k)$ -good hierarchy_:

###### Definition 1

Let $\mathcal{S}\subseteq 2^{V_{G}}$ and a $k$ be a positive integer. A
_$(\mathcal{S},k)$ -good hierarchy_ of $E_{G}-E_{T}$ is the hierarchical edge
set $E_{G}-E_{T}=E_{0}\supseteq E_{1}\supseteq E_{2}\supseteq,\dots,\supseteq
E_{h}=\emptyset$ satisfying the following conditions

  * •

The subset $E_{i+1}\subseteq E_{i}$ is a constant fraction size666We use the
statement “a subset $X^{\prime}\subseteq X$ has a constant fraction size (of
$X$)” to mean $|X^{\prime}|\leq(1-c)|X|$ for some constant $c>0$. for any
$i\in[0,h-1]$. Note that this condition inherently deduces the property of
$h=O(\log n)$.

  * •

For any $S\in\mathcal{S}$ such that $|\partial_{E_{i}}(S)|>k$,
$|\partial_{E_{i+1}}(S)|>0$ holds.

The collection of $k$-threshold outdetect labeling schemes for all
$G_{i}=(V_{G},E_{i})$ forms a $\mathcal{S}_{f,T}$-outdetect labeling scheme
for $G-E_{T}$ with $O(k\log^{2}n)$-bit label size and $O(k^{2}\log n)$
decoding time. The decoding process tries to obtain the edge(s) in
$\partial_{G_{i}}(S)$ in the decreasing order of $i$. For the largest $i$ such
that $\partial_{G_{i}}(S)$ is non-empty, the corresponding $k$-threshold
outdetect labeling returns a subset of $\partial_{G}(S)$ correctly. Formally,
the following lemma holds:

###### Lemma 2

Assume that any $k$-threshold outdetect labeling scheme
$(\hat{L}^{\mathsf{out}}_{H},\hat{D}^{\mathsf{out}})$ of label size $\alpha$
and query processing time $\beta$ is available. If there exists an algorithm
of constructing a $(\mathcal{S},k)$-good hierarchy for $\mathcal{S}\subseteq
2^{V_{G}}$ and $E_{G}-E_{T}$, there exists an $\mathcal{S}$-outdetect labeling
scheme $(L^{\mathsf{out}}_{G-E_{T}},D^{\mathsf{out}})$ for $G-E_{T}$ whose
label size is $O(\alpha\log n)$ bits and query processing time is $O(\beta\log
n)$.

###  4.3 Second Technique: Deterministic Construction of
$(\mathcal{S}_{f,T},k)$-good Hierarchy

A crucial requirement of the logarithmic-depth hierarchy $E_{0}\supseteq
E_{1}\supseteq E_{2}\supseteq,\dots,\supseteq E_{h}$ is to avoid the set
$S\in\mathcal{S}_{f,T}$ such that $|\partial_{E_{i+1}}(S)|=0$ holds despite
$|\partial_{E_{i}}(S)|>k$ and to make $|E_{i+1}|$ substantially smaller than
$|E_{i}|$. It implies that $E_{i+1}\subseteq E_{i}$ must be a hitting set of
the family of edge sets $\mathcal{Z}_{i,f,k}=\\{\partial_{E_{i}}(S)\mid
S\in\mathcal{S}_{f,T},|\partial_{E_{i}}(S)|>k\\}$ of a constant fraction size.
Allowing randomization, it suffices to construct $E_{i+1}$ by the independent
edge sub-sampling from $E_{i}$ with probability $1/2$. Such a construction
satisfies the desired property for $k=O(f\log n)$ with high probability (see
the appendix D for details). While the standard greedy algorithm can
deterministically construct the hitting set with the same guarantee, such an
approach is not tractable because the size of $\mathcal{Z}_{i,f,k}$ could be
super-polynomial, i.e.,
$|\mathcal{Z}_{i,f,k}|=\Theta(|\mathcal{S}_{f,T}|)=\Theta(n^{f})$ can hold.
The second key ingredient of our construction is to provide a polynomial-time
deterministic algorithm of constructing the hitting set for
$k=\tilde{O}(f^{2})$ through the geometric representation based on the _Euler-
tour structure_ by Duan and Pettie [19]. In this structure, each undirected
edge $e$ in $T$ is replaced by two directed edges with opposite orientations.
We refer to the tree $T$ after the replacement as $\vec{T}$, and extend the
definition of $\partial_{T}(S)$ into the directed case
$\partial_{\vec{T}}(S)$, which consists of all the directed edges obtained by
the replacement of an edge in $\partial_{T}(S)$. All the edges in $\vec{T}$
are ordered by any Euler tour $\mathit{ET}$ of $\vec{T}$ starting from the
root $r$, and each vertex in the tree is assigned with the smallest order of
the incident in-edge (i.e. the edge coming from its parent) as its one-
dimensional coordinate in the range $[1,2n-2]$. We denote the one-dimensional
coordinate of a vertex $v\in V_{\vec{T}}$ by $c(v)$. Then, one can map each
non-tree edge $e=(u,v)$ into the 2D-point $(c(u),c(v))$ in the range
$[1,2n-2]\times[1,2n-2]$ (assuming the $x$-coordinate is always smaller than
the $y$-coordinate to make the mapping well-defined). An example of the
geometric representation for the instance of Figure 1 is presented in Figure
2. For any $a\in[1,2n-2]$ and $z\in\\{x,y\\}$, let $\mathit{hs}(z,a)$ be the
axis-aligned halfspace defined by $z\geq a$. Then it is observed that the
point set $\partial_{E_{i}}(S)$ for any $S\in\mathcal{S}_{f,T}$ lies in the
symmetric difference of at most $4f$ axis-aligned halfspaces. More precisely,
the following lemma holds:

###### Lemma 3

For any vertex subset $S\subseteq V_{G}$ and edge subset $E^{\prime}\subseteq
E_{G^{\ast}}$, the following equality holds.

$\displaystyle\partial_{E^{\prime}}(S)=E^{\prime}\cap\left(\triangle_{e\in\partial_{\vec{T}}(S),z\in\\{x,y\\}}\
{\mathit{hs}(z,c(e))}\right).$

where $\triangle$ represents the symmetric difference of sets.

This lemma implies that every $\partial_{E_{i}}(S)$ for
$S\in\mathcal{S}_{f,T}$ is associated with a “checkered shape” in the plane
with at most $2f$ vertical (or horizontal) alternations. In Figure 2, the
region colored by white corresponds to the outgoing edges of $S$ such that
$\partial_{\vec{T}}(S)$ consists of two directed edges with numbers 3 and 18.
Then the problem of constructing the hitting set is seen as the construction
of _$\epsilon$ -nets_ [33].

######  Definition 2 ($\epsilon$-nets)

Let $\mathcal{Z}$ be a class of geometric shapes (e.g., rectangles or disks)
in some space, and $X$ be a set of points in the space. An _$\epsilon$ -net_
for $(X,\mathcal{Z})$ is a subset $X^{\prime}\subseteq X$ such that for any
$Z\in\mathcal{Z}$, $Z\cap X^{\prime}\neq\emptyset$ holds if $|Z\cap
X|\geq\epsilon|X|$.

Let us define the class $\mathcal{H}_{q}$ which consists of all the shapes
formed by the symmetric difference of at most $q$ horizontal halfspaces
$\mathit{hs}(y,a_{0}),\mathit{hs}(y,a_{1}),\dots,\mathit{hs}(y,a_{q^{\prime}-1})$
($q^{\prime}\leq q$, $a_{i}\in[1,2n-2]$) and the corresponding vertical
halfspaces
$\mathit{hs}(x,a_{0}),\mathit{hs}(x,a_{1}),\dots,\mathit{hs}(x,a_{q^{\prime}-1})$.
Recalling that the construction of $E_{i+1}$ is equivalent to the computation
of a hitting set of a constant fraction size for the family
$\mathcal{Z}_{i,f,k}=\\{\partial_{E_{i}}(S)\mid
S\in\mathcal{S}_{f,T},|\partial_{E_{i}}(S)|>k\\}$, our goal is to construct
the hitting set of a constant fraction size for $\\{Z\cap E_{i}\mid
Z\in\mathcal{H}_{2f},|Z\cap E_{i}|\geq k\\}$, i.e., to construct an
$\epsilon$-net of a constant fraction size for $(E_{i},\mathcal{H}_{2f})$ and
$\epsilon=k/|E_{i}|$.

Figure 2: The geometric interpretation of cutsets. The blue number is the
ordering of the directed tree edges by an Euler tour. The non-tree edges
$e^{\prime}_{1}$, $e^{\prime}_{3}$, $e^{\prime}_{5}$, $e^{\prime}_{9}$ and
$e^{\prime}_{12}$ are respectively mapped into the points shown in the right-
side coordinate system.

While there are a few deterministic polynomial-time algorithms of constructing
nearly-optimal $\epsilon$-nets for a given class of shapes [41, 14], their
running times exponentially depend on the VC dimension of the given class. The
VC dimension of $\mathcal{H}_{2f}$ is $\Omega(f)$, and thus those algorithms
cannot be applied777More precisely, they takes $\Omega(1/\epsilon)^{d}$ time
for the class with VC dimension $d$. This would efficiently work if
$1/\epsilon$ is small, but in our use $1/\epsilon$ is roughly close to $m/f$,
and thus they are not tractable for $f=\omega(1)$.. To circumvent this issue,
we regard any shape in $\mathcal{H}_{2f}$ as the union of $(2f+1)^{2}/2$
disjoint axis-aligned rectangles. For any $H\subseteq\mathcal{H}_{2f}$
containing at least $\gamma(2f+1)^{2}/2$ points ($\gamma\geq 1$), there exists
at least one axis-aligned rectangle as a subset of $H$ which contains at least
$\gamma$ points. Hence the construction of an $O(\gamma/|E_{i}|)$-net of a
constant fraction size for all axis-aligned rectangles deduces an $O(\gamma
f^{2}/|E_{i}|)$-net of a constant fraction size for $\mathcal{H}_{2f}$. In
other words, we can obtain a deterministic polynomial-time algorithm of
constructing $(\mathcal{S}_{f,T},O(\gamma f^{2}))$-good hierarchy from any
deterministic polynomial-time algorithm of constructing a $(\gamma/N)$-net of
a constant fraction size for $N$ points and all axis-aligned rectangles.

Since the VC-dimension of axis-aligned rectangles is a constant, it is
possible to use the general de-randomization technique as stated above. The
optimal $\epsilon$-net for $N$ points and axis-aligned rectangles is of size
$O(\log\log N/\epsilon)$ (i.e., $O(\log\log N/N)$-net of a constant fraction
size), which is known to be deterministically constructed [42]. However, the
construction time takes a high-exponent polynomial. Hence we also present a
simpler alternative construction which provides a $O(\log N/N)$-net of a
constant fraction size for axis-aligned rectangles in a near linear time. In
summary, we obtain the following lemma:

######  Lemma 4 (Partly By Moustafa, Dutta, and Ghosh [42])

There exist two deterministic algorithms of constructing an $O(\gamma/N)$-net
of a constant fraction size for any $N$ points and all axis-aligned
rectangles, each of which attains the following performance guarantee.

  * •

$\gamma=\log\log N$ and the construction time is $\mathrm{poly}(N)$.

  * •

$\gamma=\log N$ and the construction time is $\tilde{O}(N)$.

By the argument above, we obtain the following lemma.

###### Lemma 5

There exist two deterministic algorithms respectively constructing a
$(\mathcal{S}_{f,T},k)$-good hierarchy with the following performance
guarantees:

  * •

$k=O(f^{2}\log n)$ and the construction time is $\tilde{O}(m)$.

  * •

$k=O(f^{2}\log\log n)$ and the construction time is $\mathrm{poly}(m)$.

##  5 Wrap-Up

We summarize how all the components are combined into the $f$-FTC labeling
scheme. We present below the case of the $f$-FTC labeling scheme of label size
$O(f^{2}\log^{3}n)$. Yet another scheme of label size
$O(f^{2}(\log^{2})\log\log n)$ is constructed in the same way. Consider any
input graph $G$ of $n$ vertices and $m$ edges. The whole construction
algorithm works as the following steps:

  1. 1.

Construct any spanning tree $T$ of $G$, and transform $G$ and $T$ into the
auxiliary graph $G^{\prime}$ and its spanning tree $T^{\prime}$ explained in
Section 3.2. Note that the graph $G^{\prime}$ satisfies
$|V_{G^{\prime}}|=O(m)$ and $|E_{G^{\prime}}|=O(m)$.

  2. 2.

Utilizing the algorithm of Lemma 5, construct a $(\mathcal{S}_{f,T},cf^{2}\log
n)$-good hierarchy $E_{0}\supseteq E_{1}\supseteq
E_{2}\supseteq,\dots,\supseteq E_{h}$ for $E_{G^{\prime}}-E_{T^{\prime}}$,
where $c$ is a hidden constant. The construction time is
$\tilde{O}(|E_{G^{\prime}}|)=O(m)$.

  3. 3.

Let $G_{i}=(V_{G^{\prime}},E_{i})$ $(0\leq i\leq h)$. Construct
$L^{\mathsf{RS}(cf^{2}\log n)}_{G_{i}}$ for all $i$. By the construction of
step 2 and Lemma 2, we obtain the $\mathcal{S}_{f,T}$-outdetect labeling
scheme of $O(f^{2}\log^{3}n)$-bit label size. The construction time is in
$\tilde{O}(mkh)=\tilde{O}(mf^{2})$, and the decoding time is
$\tilde{O}(f^{4})$ due to Proposition 2 and Lemma 2.

  4. 4.

Construct the ancestry labeling scheme for $T^{\prime}$ by the algorithm of
[39], which takes $O(m)$ time.

  5. 5.

By Lemma 1, the labels constructed in the steps 3 and 4 form a tree edge
$f$-FTC labeling scheme for $G^{\prime}$ and $T^{\prime}$. Then we also obtain
the $f$-FTC labeling scheme for $G$ by Corollary 3.

Finally we have the following theorem.

###### Theorem 2

There exist two deterministic $f$-FTC labeling schemes for any graph $G$ of
$n$ vertices and $m$ edges which respectively attain the following bounds:

  * •

The label size is $O(\log n)$ bits per vertex, and $O(f^{2}(\log^{2}n)\log\log
n)$ bits per edge. The query processing time is $\tilde{O}(|F|f^{4})$, where
$F$ is the set of queried edges satisfying $|F|\leq f$. The construction time
is polynomial of $m$.

  * •

The label size is $O(\log n)$ bits per vertex, and $O(f^{2}\log^{3}n)$ bits
per edge. The query processing time is $\tilde{O}(|F|f^{4})$. The construction
time is near linear, i.e., $\tilde{O}(mf^{2})$.

This theorem is a weaker form of Theorem 1. In the next section we present how
one can improve this to Theorem 1 claiming faster query processing time.

##  6 Improving Query Processing Time

The algorithmic idea of this improvement is twofold: The first idea attains
the _adaptiveness_ of $\mathcal{S}_{f,T}$-outdetect labeling scheme, i.e., to
get rid of the dependency on $f$ in the decoding time. There is a simple
technique of transforming any $\mathcal{S}_{f,T}$-outdetect labeling scheme
with $\tilde{O}(f^{c})$ decoding time into the one with
$\tilde{O}(|\partial_{T}(S)|^{c})$ decoding time for any given query
$S\in\mathcal{S}_{f,T}$: Instead of single labeling, we prepare the multiple
instances of the (non-adaptive) $\mathcal{S}_{f^{\prime},T}$-outdetect
labeling scheme for $f^{\prime}=2,4,\dots,f$. If the original labeling scheme
has a $\Omega(f)$-bit label size, this transformation does not cause any
asymptotic blow-up of label size. Assume that a query
$S\subseteq\mathcal{S}_{f,T}$ is given. Since
$S\in\mathcal{S}_{|\partial_{T}(S)|,T}$ necessarily holds, the adaptive scheme
can find the outgoing edge of $S$ by utilizing the
$\mathcal{S}_{f^{\prime},T}$-outdetect labeling scheme for $f^{\prime}$ such
that $f^{\prime}/2<|\partial_{T}(S)|\leq f^{\prime}$ holds, which runs in
$\tilde{O(}(|\partial_{T}(S)|^{c})$ time 888In reality, this transformation is
not necessary if we utilize our deterministic $\mathcal{S}_{f,T}$-outdetect
labeling scheme based on the Reed-Solomon code. More precisely, it inherently
admits the adaptive decoding without any modification of the label
construction. See the appendix E for details..

The second idea is to utilize the adaptive scheme for further acceleration of
the decoding time. In processing the query of $(s,t,F)$, every query
$S\subseteq V_{G}$ issued to the $\mathcal{S}_{f,T}$-outdetect labeling scheme
necessarily belongs to $\mathcal{S}_{|F|,T}$. Hence The adaptive decoding of
the $\mathcal{S}_{f,T}$-outdetect labeling scheme always runs in
$\tilde{O}(|F|^{4})$ time for the deterministic cases, and in
$\tilde{O}(|F|^{2})$ time for the randomized case. Since the decoding time of
the tree edge $f$-FTC labeling scheme is dominated by $|F|$ queries to the
$\mathcal{S}_{f,T}$-outdetect labeling scheme, the straightforward
implementation respectively results in the decoding time of
$\tilde{O}(|F|^{5})$ and $\tilde{O}(|F|^{3})$. We shave off this extra $|F|$
factor by a simple refinement of the decoding process of the tree edge $f$-FTC
labeling scheme: In the refined process, the outgoing edge detection for
merging fragments is always applied to the fragment $S$ such that
$|\partial_{T}(S)|$ is the smallest of all the fragments currently managed,
while the original process always applies it to the fragment with $s$. By a
careful analysis, we obtain the following lemma:

###### Lemma 6

Assume that there exists a $\mathcal{S}_{f,T}$-outdetect labeling scheme of
label size $\alpha=\tilde{O}(f^{b})$ and decoding time
$\beta=\tilde{O}(f^{c})$. Then there exists a $f$-FTC labeling scheme of
$O(\alpha+\log n)$-bit label size and $\tilde{O}(|F|^{b+1}+|F|^{c})$ decoding
time. The resultant $f$-FTC labeling scheme is deterministic if the
corresponding $\mathcal{S}_{f,T}$-outdetect labeling scheme is deterministic.

The three $\mathcal{S}_{f,T}$-outdetect labeling schemes we presented in this
paper (including the randomized case) attain
$(\alpha,\beta)=(O(f^{2}(\log^{2}n)\log\log
n),\tilde{O}(f^{4})),(O(f^{2}\log^{3}n),\tilde{O}(f^{4}))$, and
$O(f\log^{3}n),\tilde{O}(f^{2}))$. By this lemma, they respectively deduce the
schemes as claimed in Table 1.

##  7 Concluding Remarks

This paper presented a new deterministic $f$-FTC labeling scheme which attains
$O(f^{2}\mathrm{polylog}(n))$-bit label size, polynomial-time construction,
and $\tilde{O}(\mathrm{poly}(|F|))$-time query processing time for a given
faulty edge set $F$. This is the first deterministic and polynomial-time
$f$-FTC labeling scheme with a non-trivial label size. The scheme is developed
on the top of a general framework, and only by the modification of graph
sparsification, we can also obtain a randomized $f$-FTC labeling scheme which
is competitive to the original Dory-Parter scheme and attains an adaptive
query processing time. The key technical ingredient is a new deterministic
$\mathcal{S}$-outdetect labeling scheme based on error-correcting codes. From
the authors’ perspective, our results pose a few promising future research
directions. We conclude this paper with summarizing them.

  * •

Is it possible to develop a deterministic algorithm yielding better edge
hierarchies, i.e., the hierarchy such that for any $S$ there exists $i$
satisfying $0<|\partial_{E_{i}}(S)|=o(f^{2}\log n)$? Our framework
automatically deduces a deterministic $f$-FTC labeling scheme with an improved
label size if such an algorithm is found.

  * •

Considering the distributed implementation of our deterministic scheme in the
standard CONGEST model, the straightforward implementation takes
$\tilde{O}(m)$ rounds mainly due to the construction of the
$(\mathcal{S}_{f,T},\tilde{O}(f^{2}))$-good hierarchy. While it can be
optimized to $\tilde{O}(\sqrt{m}+f^{2}D)$ rounds, there still exists a large
gap with the randomized construction of $\tilde{O}(f+D)$ rounds. Is it
possible to obtain the deterministic $f$-FTC labeling scheme of
$O(\mathrm{poly}(f,\log n))$-bit label size which is implemented in the
CONGEST model with $\tilde{O}(\mathrm{poly}(f)+D)$ or
$\tilde{O}(\mathrm{poly}(f)\cdot D)$ rounds?

  * •

Can we obtain any non-trivial lower bound for the label size of $f$-FTC
labeling schemes with full query support? It seems plausible that the
$\Omega(f)$-bit lower bound holds, but no promising way of proving this is
found so far.

  * •

Can we use our technique to obtain a (deterministic) fault-tolerant
connectivity labeling scheme for _vertex faults_? As pointed out in [46],
there exists a large technical gap between edge fault tolerance and vertex
fault tolerance. It is still open to obtain a scheme with a label size
sublinear of $n$, even for moderately small $f$ (e.g., $f=O(\log n))$.

  * •

Can our technique be exported to other applications of $\mathcal{S}$-outdetect
labeling schemes, such as centralized fault-tolerant connectivity oracles
[20], distributed computation of sparse spanning subgraphs [37, 27, 24, 43] or
small cut detection [48, 45], and dynamic algorithms [36, 25], for obtaining
any improved result?

##  Appendix A Formal Specification of Labeling Schemes

###  A.1 Fault-Tolerant Connectivity Labeling

A _$f$ -fault-tolerant connectivity labeling scheme_ ($f$-FTC labeling scheme)
for a given input graph $G$ consists of a labeling function
$L^{\mathsf{con}}_{G,f}:V_{G}\cup E_{G}\to\\{0,1\\}^{\ast}$ and a universal
decoding function
$D^{\mathsf{con}}_{f}:\\{0,1\\}^{\ast}\times\\{0,1\\}^{\ast}\times\\{0,1\\}^{\ast}\to\\{0,1\\}$.
For an edge subset $F=\\{e_{1},e_{2},\dots,e_{|F|}\\}\subseteq E_{G}$, let
$L^{\mathsf{con}}_{G,f}(F)$ be the concatenation of the labels
$L^{\mathsf{con}}_{G,f}(e_{1})\circ
L^{\mathsf{con}}_{G,f}(e_{2})\circ\dots\circ L^{\mathsf{con}}_{G,f}(e_{|F|})$
in an arbitrary order. For a query $(s,t,F)$ of $s,t\in V_{G}$ and an edge
subset $F\subseteq E_{G}$ of cardinality at most $f$, the decoder function
returns the $s$-$t$ connectivity in $G-F$ by giving the labels of $s$, $t$ and
all the edges in $F$, i.e., $D^{\mathsf{con}}$ satisfies that
$D^{\mathsf{con}}(L^{\mathsf{con}}_{G}(s),L^{\mathsf{con}}_{G}(t),L^{\mathsf{con}}_{G}(F))=1$
if and only if $s$ and $t$ are connected in $G-F$. The _label size_ of the
scheme is defined as the maximum length of the labels assigned to vertices and
edges.

###  A.2 Ancestry labeling

Given any rooted tree $T$, this labeling scheme assigns all vertices with the
labels such that the ancestor-descendant relationship between any two vertices
is determined only from their labels. More precisely, the ancestry labeling
scheme for $T$ consists of a labeling function
$L^{\mathsf{anc}}_{T}:V_{T}\to\\{0,1\\}^{\ast}$ and a universal decoding
function
$D^{\mathsf{anc}}:\\{0,1\\}^{\ast}\times\\{0,1\\}^{\ast}\to\\{-1,0,1\\}$ (not
dependent on $T$). It determines if two given vertices $x,y\in V_{T}$ have the
ancestor-descendant relationship or not from their labels, i.e.,
$D^{\mathsf{anc}}(L^{\mathsf{anc}}_{T}(x),L^{\mathsf{anc}}_{T}(y))=1$ if $x$
is an ancestor of $y$, $-1$ if $y$ is an ancestor of $x$, or $0$ otherwise
(including the case of $x=y)$. The following lemma is well-known:

######  Lemma 7 (Kannan, Naor, and Rudich [39])

Let $T$ be a rooted tree of $n$ vertices. There exists a deterministic
ancestry labeling scheme with label size of $O(\log n)$ bits. Computing
$L^{\mathsf{anc}}_{T}(x)$ for all $x\in V_{T}$ takes $O(n)$ time, and
$D^{\mathsf{anc}}(L^{\mathsf{anc}}_{T}(x),L^{\mathsf{anc}}_{T}(y))$ for each
$x,y\in V_{T}$ takes $O(1)$ time. The labeling function $L^{\mathsf{anc}}_{T}$
is injective for any $T$, i.e., a unique label assignment.

###  A.3 $\mathcal{S}$-Outdetect Labeling

Let $\mathbb{F}$ be any finite field of characteristic two whose addition and
multiplication operators are respectively denoted by “$+$” and “$\cdot$” 999A
field $\mathbb{F}$ has characteristic two if and only if any element
$x\in\mathbb{F}$ satisfies $x+x=0$, or equivalently $x=x^{-1}$ (where $0$ is
the unit element and $x^{-1}$ is the inverse element of $x$)., and
$\mathcal{E}$ be the domain of unique edge IDs not depending on $G$101010Since
the size of this domain inherently depends on $n$, it should be defined
precisely as $\mathcal{E}_{n}$, which is the universal domain valid for all
the graphs with at most $n$ vertices. But we intentionally omit such a
dependency for avoiding non-essential complication.. An
$\mathcal{S}$-outdetect labeling scheme consists of a vertex labeling function
$L^{\mathsf{out}}_{G}:V_{G}\to\mathbb{F}^{\ell}$ and a universal decoding
function $D^{\mathsf{out}}:\mathbb{F}^{\ell}\to\mathcal{E}$, where $\ell$ is a
positive integer representing the size of labels. It must satisfy the
following two conditions:

  * •

For any $S\subseteq\mathcal{S}$, $D^{\mathsf{out}}(\sum_{v\in
S}L^{\mathsf{out}}_{G}(v))$ returns the ID of an outgoing edge of $S$ in $G$
if $\partial_{G}(S)$ is nonempty.

  * •

If $\partial_{G}(S)=\emptyset$, $D^{\mathsf{out}}(\sum_{v\in
S}L^{\mathsf{out}}_{G}(v))$ returns formal zero, which is a special value in
$\mathcal{E}$ never assigned to actual edges.

For short, we use the notation $L^{\mathsf{out}}_{G}(S)$ to represent
$\sum_{v\in S}L^{\mathsf{out}}_{G}(v)$ in the following argument. By
definition, $D^{\mathsf{out}}(L^{\mathsf{out}}_{G}(V_{G}))=0$ must hold. The
_$k$ -threshold outdetect labeling scheme_ for $G$ is a restricted variant of
$2^{V_{G}}$-outdetect labeling scheme, which guarantees that
$D^{\mathsf{out}}(L^{\mathsf{out}}_{G}(S))$ returns an outgoing edge of $S$
only if $0<|\partial_{G}(S)|\leq k$ holds, or returns zero if
$|\partial_{G}(S)|=0$. In the case of $|\partial_{G}(S)|>k$, the returned
value is undefined, i.e., an arbitrary value is returned.

##  Appendix B Omitted Details

###  B.1 Constructing Tree Edge $f$-FTC labeling Scheme

The goal of this section is to show Lemma 1.

###### Lemma 0

Assume any deterministic $\mathcal{S}_{f,T}$-outdetect labeling scheme
$(L^{\mathsf{out}}_{G},D^{\mathsf{out}})$ of label size $\alpha$ and decoding
time $\beta$. Then there exists a deterministic tree edge $f$-FTC labeling
scheme of $(\alpha+O(\log n))$-bit label size and $O(|F|(\beta+\log|F|))$
decoding time, where $F$ is a set of faulty edges given by a query.

For the proof, we first present the precise details of the framework. Let
$G^{\ast}=G-E_{T}$ for short. The tree edge $f$-FTC labeling scheme is
implemented by any $\mathcal{S}_{f,T}$-outdetect labeling scheme for
$G^{\ast}$ and any ancestry labeling scheme for $T$. Let
$(L^{\mathsf{anc}}_{T},D^{\mathsf{anc}})$ be the ancestry labeling scheme.
Without loss of generality, we assume that $L^{\mathsf{anc}}_{T}(v)$ for all
$v$ has a fixed bit length $p=O(\log n)$. We assign the edge ID
$L^{\mathsf{anc}}_{T}(u)\circ L^{\mathsf{anc}}_{T}(v)\in\\{0,1\\}^{2p}$ to
each edge $(u,v)\in E_{G^{\ast}}$. The uniqueness of the edge ID follows the
uniqueness of the ancestry labeling guaranteed in Lemma 7. For the edge ID
domain $\mathcal{E}=\\{0,1\\}^{2p}$, we construct the
$\mathcal{S}_{f,T}$-outdetect labeling scheme
$(L^{\mathsf{out}}_{G^{\ast}},D^{\mathsf{out}})$. The labeling function
$L^{\mathsf{con}}_{G}(v)$ of our tree edge $f$-FTC labeling scheme is defined
as follows:

  * •

$L^{\mathsf{con}}_{G}(v)=L^{\mathsf{anc}}_{T}(v)$.

  * •

For any $e=(u,v)\in E_{T}$,
$L^{\mathsf{con}}_{G}(e)=L^{\mathsf{anc}}_{T}(u)\circ
L^{\mathsf{anc}}_{T}(v)\circ L^{\mathsf{out}}_{G^{\ast}}(V_{T(e)})$. Recall
that any tree edge $f$-FTC labeling scheme does not have to assign labels to
non-tree edges.

We see how to implement the decoding function. Assume that a query $(s,t,F)$
of $|F|\leq f$ is given. Let $\mathcal{C}(F)=\\{C_{0},C_{1},\dots,C_{|F|}\\}$
be the collection of the fragments (i.e., the vertex subset inducing a
connected component of $T-F$). Let $V(F)$ be the set of the endpoints of the
edges in $F$. By introducing any total order over $\\{0,1\\}^{p}$, we define
the ID of $C_{i}\in\mathcal{C}(F)$ as the maximum ancestry label in
$V_{C_{i}}\cap V(F)$, and abuse $C_{i}$ itself as the ID of $C_{i}$. The
_component graph_ $H/\mathcal{C}(F)$ of a spanning subgraph $H\subseteq G$ is
the multigraph obtained from $H$ by contracting each vertex set $C_{i}$
($0\leq i\leq|F|$) into a single vertex and then removing self-loops. The
following proposition is known:

######  Proposition 3 (Claim 3.14 in [21])

Let $(s,t,F)$ be any given query, and $|F|\leq f$. Then $T/\mathcal{C}(F)$ is
computed deterministically in $O(|F|\log|F|)$ time. In addition, there exists
a deterministic algorithm which is given $L^{\mathsf{anc}}_{T}(v)$ and returns
in $O(\log|F|)$ time the ID of $C_{i}\in\mathcal{C}(F)$ containing $v$.

The proposition above admits the detection of the two connected components in
$T-F$ respectively containing $s$ and $t$. We assume $s\in C_{0}$ and $t\in
C_{1}$ without loss of generality. Starting from $C_{0}$, the decoding
procedure grows the component containing $s$ iteratively by finding its
outgoing edge: Initially, let $S=C_{0}$. The procedure detects an outgoing
edge $(u,v)$ of $S$ in $G^{\ast}$, where $u$ is the vertex in $S$ and $v\in
C_{j}$ for some $j\in[0,f^{\prime}]$, until no outgoing edge is found. When
the edge $(u,v)$ is found, $S$ is updated with $S\cup\\{C_{j}\\}$. Obviously,
$s$ and $t$ are connected in $G-F$ if and only if this process merges $C_{1}$
with $S$. Throughout this process, $\partial_{T}(S)\subseteq F$ obviously
holds and thus $S\in\mathcal{S}_{f,T}$ always holds. Hence one can use the
$\mathcal{S}_{f,T}$-outdetect labeling scheme to find an outgoing edge
$(u,v)$. The primary matter is how to manage $L^{\mathsf{out}}_{G^{\ast}}(S)$.
We resolve it with a technique similar to [21] (Claim 3.15). The following
proposition holds.

###### Proposition 4

For any $X\subseteq V_{T}$,
$L^{\mathsf{out}}_{G^{\ast}}(X)=\sum_{e\in\partial_{T}(X)}L^{\mathsf{out}}_{G^{\ast}}(V_{T(e)})$
holds.

###### Proof.

Let $k=|\partial_{T}(X)|$. The proof is based on the induction on $k$. (Basis)
$k=0$: Then $X=V_{G}$ holds. Since we have
$L^{\mathsf{out}}_{G^{\ast}}(V_{T})=0$ by the definition of the
$\mathcal{S}_{f,T}$-outdetect labeling scheme, the proposition obviously
holds. (Inductive step) Suppose that the proposition holds for any
$X^{\prime}$ such that $|\partial_{T}(X^{\prime})|=k$, and consider $X$ such
that $|\partial_{T}(X)|=k+1$ holds. Let
$\partial_{T}(X)=\\{e_{1},e_{2},\dots,e_{k+1}\\}$. Without loss of generality,
we assume that there is no descendant of $e_{k+1}$ in $\partial_{T}(X)$, i.e.,
$T(e_{k+1})$ does not contain any edge in $\partial_{T}(X)$. Let
$e_{k+1}=(u,v)$ where $v$ is the lower vertex of $e_{k+1}$. We consider the
case of $v\in X$. Let $W=X\setminus V_{T(e_{k+1})}$. Since we have
$\partial_{T}(W)=\partial_{T}(X)\setminus\\{e_{k+1}\\}$, $|\partial_{T}(W)|=k$
holds. Thus by the induction hypothesis we obtain
$L^{\mathsf{out}}_{G^{\ast}}(W)=\sum_{e\in\partial_{T}(W)}L^{\mathsf{out}}_{G^{\ast}}(V_{T(e)})$.
Since $W$ and $V_{T(v)}$ are disjoint by definition, we have

$\displaystyle L^{\mathsf{out}}_{G^{\ast}}(X)$
$\displaystyle=L^{\mathsf{out}}_{G^{\ast}}(W)+L^{\mathsf{out}}_{G^{\ast}}(V_{T(e_{k+1})})$
$\displaystyle=\sum_{e\in\partial_{T}(W)}L^{\mathsf{out}}_{G^{\ast}}(V_{T(e)})+L^{\mathsf{out}}_{G^{\ast}}(V_{T(e_{k+1})})$
$\displaystyle=\sum_{e\in\partial_{T}(X)}L^{\mathsf{out}}_{G^{\ast}}(V_{T(e)}).$

The case of $v\not\in X$ is proved similarly. ∎

We prove Lemma 1 by the proposition above.

###### Proof.

By Proposition 4, one can compute the $L^{\mathsf{out}}_{G^{\ast}}(C_{i})$ for
all $i\in[0,|F|]$ from the labels of the edges in $F$. Assume an outgoing edge
$e=(u,v)$ of $S$ ($v\not\in S$) is detected by the
$\mathcal{S}_{f,T}$-outdetect labeling. Since we can obtain the ID
$L^{\mathsf{anc}}_{T}(u)\circ L^{\mathsf{anc}}_{T}(v)$ of $e$, the ancestry
label $L^{\mathsf{anc}}_{T}(v)$ is available. By Proposition 3, it also gives
the ID of the component in $\mathcal{C}(F)$ which contains $v$. Let us assume
$v\in C_{j}$. When merging $C_{j}$ into $S$, we have known both
$L^{\mathsf{out}}_{G^{\ast}}(S)$ and $L^{\mathsf{out}}_{G^{\ast}}(C_{j})$.
Thus the label $L^{\mathsf{out}}_{G^{\ast}}(S)$ is updated by adding
$L^{\mathsf{out}}_{G^{\ast}}(C_{j})$. The query processing time is spent for
$|F|$ times of querying the $\mathcal{S}_{f,T}$-outdetect labeling scheme,
which takes $O(|F|(\beta+\log|F|))$ time in total. The initial set-up takes
$O(|F|\log|F|+|F|\beta)$ time, where the term $|F|\log|F|$ is for computing
the component graph, and $|F|\beta$ is for computing the
$\mathcal{S}_{f,T}$-outdetect labels of all fragments. The label size is
obviously $O(\alpha+\log n)$. ∎

###  B.2 Construction of Deterministic $\mathcal{S}_{f,T}$-Outdetect Labeling
Scheme

###### Lemma 0

Assume that any $k$-threshold outdetect labeling scheme
$(\hat{L}^{\mathsf{out}}_{H},\hat{D}^{\mathsf{out}})$ of label size $\alpha$
and query processing time $\beta$ is available. If there exists an algorithm
of constructing a $(\mathcal{S},k)$-good hierarchy for $\mathcal{S}\subseteq
2^{V_{G}}$ and $E_{G}-E_{T}$, there exists an $\mathcal{S}$-outdetect labeling
scheme $(L^{\mathsf{out}}_{G-E_{T}},D^{\mathsf{out}})$ for $G-E_{T}$ whose
label size is $O(\alpha\log n)$ bits and query processing time is $O(\beta\log
n)$.

###### Proof.

Assume that a $(\mathcal{S},k)$-good hierarchy $E_{0}\supseteq E_{1}\supseteq
E_{2}\supseteq,\dots,\supseteq E_{h}$ is obtained. Let $G_{i}=(V_{G},E_{i})$.
The labeling function $L^{\mathsf{out}}_{G^{\ast}}$ is defined as the
concatenation of the labels by $\hat{L}^{\mathsf{out}}_{G_{i}}$ for all
$i\in[0,h]$, i.e.,
$L^{\mathsf{out}}_{G-E_{T}}(v)=\hat{L}^{\mathsf{out}}_{G_{0}}(v)\circ\hat{L}^{\mathsf{out}}_{G_{1}}(v)\circ\dots,\circ\hat{L}^{\mathsf{out}}_{G_{h}}(v)$
(where $\circ$ is the binary operator of concatenating two strings). To detect
an outgoing edge of $S\in\mathcal{S}$, it suffices to compute the value of
$\hat{D}^{\mathsf{out}}(\bigoplus_{v\in S}\hat{L}^{\mathsf{out}}_{G_{i}}(v))$
such that it returns a non-zero value and
$\hat{D}^{\mathsf{out}}(\bigoplus_{v\in S}L^{\mathsf{out}}_{G_{j}}(v))$ for
any $j>i$ returns zero. The condition of the hierarchy implies
$0<|E_{i}\cap\partial_{G}(S)|\leq k$, and thus
$\hat{D^{\mathsf{out}}}(\bigoplus_{v\in S}L^{\mathsf{out}}_{G_{i}}(v))$
correctly returns all the outgoing edges of $S$ in $E_{i}\subseteq E_{G}$. The
bounds for the label size and the query processing time are obvious. ∎

###  B.3 $k$-threshold outdetect labeling: Choice of Codes

Following the construction presented in Section 4.2, any linear code of the
minimum distance $2k$ naturally induces a $k$-threshold outdetect labeling
scheme for any graph $G$. The label size is determined by the number of
columns of the parity check matrix $C$ of the code. Obtaining both a smaller
number of rows and a larger minimum distance is roughly equivalent to
achieving a good code rate. Hence, as a general principle, any high-rate code
would provide a good scheme. In addition, we need to care other additional
criteria for efficient implementation of the outdetect labeling scheme, which
are stated as follows:

  * •

We use a parity check matrix which has $|\mathcal{E}|$ rows, i.e., the
codeword length is $|\mathcal{E}|$. Thus it is not appropriate to use the
error-correcting codes whose decoding time depends on the codeword length.
Ideally, the decoding time should depend only on the length of the syndrome
(i.e., the length of labels).

  * •

The construction of the label for an edge $e$ corresponds to the computation
of the row vector of $C$ corresponding to $e$. Since the number of rows
$|\mathcal{E}|$ could be much larger than the actual number of edges
$|E_{G}|$, computing the whole matrix $C$ can result in slower computation of
edge labels to all $e\in E_{G}$. To complete the label assignment in time
dependent only on the actual number $|E_{G}|$ of edges but not on
$|\mathcal{E}|$, $C$ must admit efficient “local” computation of a specified
row.

One of the error-correcting codes addressing the issues above is Reed-Solomon
code. Reed-Solomon code is a non-binary code whose alphabet is a finite field
$\mathbb{F}$ of order $|\mathcal{E}|+1$, and the number of rows is chosen
arbitrarily. Since $|\mathcal{E}|$ is a polynomial of $n$ in our application,
each code symbol is encoded with $O(\log n)$ bits, and the addition and
multiplication over $\mathbb{F}$ takes $O(1)$ time in the standard word-RAM
model. Let $C_{2k}$ be the $|\mathcal{E}|\times 2k$ parity check matrix of
Reed-Solomon code. We have the following nice features:

  * •

The minimum distance of the code defined by $C_{2k}$ is equal to $2k$. That
is, a $k$-threshold outdetect labeling scheme is deduced from $C_{2k}$. Since
each column vector of $C_{2k}$ is encoded by $O(k\log|\mathcal{E}|)$ bits, the
label size is $O(k\log n)$ bits.

  * •

Let $w$ be any $|\mathcal{E}|$-dimensional vector over $\mathbb{F}$ which
contains at most $k$ nonzero elements. There exists a deterministic algorithm
of computing all non-zero elements in $w$ (in the form of the pairs of value
and position) from $w\cdot C_{2k}$, which runs in $O(k^{2})$ time in the
standard word-RAM model [17]. The recovery of $w$ necessarily succeeds if $w$
contains at most $k$ non-zero elements, but the result can become arbitrary if
$w$ contains more than $k$ non-zero elements.

  * •

Given any $e\in\mathcal{E}$, the row vector of $C_{2k}$ corresponding to $e$
is deterministically computed in $O(k)$ time in the standard word-RAM model.

Let $(L^{\mathsf{RS}(k)}_{H},D^{\mathsf{RS}(k)})$ be the $k$-threshold
outdetect labeling scheme for $H\subseteq G$ defined by the
$|\mathcal{E}|\times 2k$ parity check matrix of Reed-Solomon code. The
features above obviously deduces Proposition 2.

###  B.4 Deterministic Construction of Good Hierarchy

We first focus on the proof of Lemma 3. Since
$\partial_{G^{\prime}}(S)=\partial_{G^{\prime}}(V_{G}\setminus S)$ holds for
any $S\subseteq V_{G}$ and any spanning subgraph $G^{\prime}$ of $G$, we
assume $S$ always contains the root $r$ wlog. We use notations $\vec{T}$,
$\mathit{ET}$, $c(v)$, $\mathit{hs}(z,a)$, and $\mathcal{H}_{2f}$ as defined
in Section 4.3. In addition, we introduce a few additional notations. Let
$\mathit{ET}=e_{1},e_{2},\dots,e_{i},\dots,e_{2n-2}$. We denote the prefix
$e_{1},e_{2},\dots,e_{i}$ of $\mathit{ET}$ up to the $i$-th element by
$\mathit{ET}(i)$. For the proof, we introduce a few auxiliary lemmas.

######  Lemma 8 (Claim 3.3 in [21])

Let $F$ be any induced cutset of $G$, and let $n_{v}(F)$ be the number of the
edges in $F$ lying on the path from the root to $v$ in $T$. Let $V_{0}=\\{v\in
V_{G}\mid\text{$n_{v}(F)$ is even}\\}$ and $V_{1}=\\{v\in
V_{G}\mid\text{$n_{v}(F)$ is odd}\\}$. Then $(V_{0},V_{1})$ is the cut of $G$
induced by $F$.

###### Lemma 9

Assume that $S\subseteq V_{T}$ contains the root $r$ of $T$. For any vertex
$v\in S$, $|\mathit{ET}(c(v))\cap\partial_{\vec{T}}(S)|$ is even if $v\in S$,
or odd otherwise.

###### Proof.

We first show that any vertex $v$ satisfies that $n_{v}(\partial_{T}(S))$ is
even if and only if $v\in S$. Let $F^{\prime}\subseteq E_{G}$ be the cutset
associated with the cut $(S,V_{G}\setminus S)$. By Lemma 8, for any vertex
$v\in S$, $n_{v}(F^{\prime})$ has the same parity. Since $n_{r}(F^{\prime})$
is obviously even, we can conclude that $n_{v}(F^{\prime})$ is even for any
$v\in S$. It also implies that $n_{v}(F^{\prime})$ has the odd parity for any
$v\in V_{G}\setminus S$. By definition,
$n_{v}(F^{\prime})=n_{v}(\partial_{T}(S))$ obviously holds.

Next, we prove the statement of the lemma. For any undirected edge $e\in
E_{T}$, let $e^{+}$ and $e^{-}$ be the downward and upward directed edges in
$E_{\vec{T}}$ corresponding to $e$ respectively. Since $e^{+}$ always precedes
$e^{-}$ in $\mathit{ET}$, only the following three cases can occur: (1) both
$e^{+}$ and $e^{-}$ precedes $e_{c(v)}$ in $\mathit{ET}$, (2) both $e^{+}$ nor
$e^{-}$ follows $e_{c(v)}$ in $\mathit{ET}$, or (3) $e^{+}$ precedes or is
equal to $e_{c(v)}$ in $\mathit{ET}$ and $e^{-}$ follows. Since the edge
$e\in\partial_{T}(S)$ to which the case (1) or (2) applies does not affect the
parity of $|\mathit{ET}(c(v))\cap\partial_{\vec{T}}(S)|$, the parity of
$|\mathit{ET}(c(v))\cap\partial_{\vec{T}}(S)|$ is equal to the number of the
edges $e\in\partial_{T}(S)$ to which the third case applies. Since the case
(3) applies to an edge $e$ if and only if $e$ is on the path from $r$ to $v$,
we obtain
$|\mathit{ET}(c(v))\cap\partial_{\vec{T}}(S)|=n_{v}(\partial_{T}(S))$. That
is, it has the even parity. The lemma is proved. ∎

Now we are ready to prove Lemma 3.

###### Lemma 0

For any vertex subset $S\subseteq V_{G}$ and edge subset $E^{\prime}\subseteq
E_{G^{\ast}}$, the following equality holds.

$\displaystyle\partial_{E^{\prime}}(S)=E^{\prime}\cap\left(\triangle_{e\in\partial_{\vec{T}}(S),z\in\\{x,y\\}}\
{\mathit{hs}(z,c(e))}\right).$

###### Proof.

Let $\mathcal{Q}_{x}=\\{\mathit{hs}(x,c(e))\mid e\in\partial_{\vec{T}}(S)\\}$,
$\mathcal{Q}_{y}=\\{\mathit{hs}(y,c(e))\mid e\in\partial_{\vec{T}}(S)\\}$, and
$Q=\triangle_{Q^{\prime}\in\mathcal{Q}_{x}\cup\mathcal{Q}_{y}}Q^{\prime}$. For
any $(u,v)\in\partial_{E^{\prime}}(S)$, exactly one of $u$ and $v$ belongs to
$S$ and the other one belongs to $V_{G}\setminus S$. By symmetry, we assume
$u\in S$ and $c(u)<c(v)$ wlog. Lemma 9 implies
$|\mathit{ET}(c(u))\cap\partial_{\vec{T}}(S)|$ is even, and
$|\mathit{ET}(c(v))\cap\partial_{\vec{T}}(S)|$ is odd. It implies that $(u,v)$
lies in the two regions respectively defined as the intersection of an even
number of halfspaces in $\mathcal{Q}_{y}$ and as the intersection of an odd
number of halfspaces in $\mathcal{Q}_{x}$. Since $\mathcal{Q}_{x}$ and
$\mathcal{Q}_{y}$ are disjoint, $(u,v)$ lies in the region defined as the
intersection of an odd number of halfspaces in
$\mathcal{Q}_{x}\cup\mathcal{Q}_{y}$, i.e., it is contained in $Q$. Similarly,
if $(u,v)$ is not an edge in $\partial_{E^{\prime}}(S)$, the parities of
$|\mathit{ET}(c(u))\cap\partial_{\vec{T}}(S)|$ and
$|\mathit{ET}(c(v))\cap\partial_{\vec{T}}(S)|$ becomes the same, and thus $e$
lies in the region defined as the intersection of an even number of halfspaces
in $\mathcal{Q}_{x}\cup\mathcal{Q}_{y}$, and thus not contained in $Q$. The
lemma is proved. ∎

Next, we focus on the deterministic $\epsilon$-net construction. We present
two known results used in our deterministic construction.

######  Lemma 10 (Mustafa, Dutta, and Ghosh [42])

Let $\epsilon>0$. There exists a deterministic polynomial-time algorithm of
constructing an $\epsilon$-net of size $O(\log\log N/\epsilon)$ for any $N$
point set and all axis-aligned rectangles.

Let $P$ be any set of points in a 2D-range
$R=[a_{1},a_{2}]\times[b_{1},b_{2}]$. A _three-sided axis-aligned rectangle_
with respect to $R$ is the axis-aligned rectangle whose one side is on the
border of $R$. The following lemma is known:

######  Lemma 11 (Kulkarni and Govindarajan [35])

Let $P$ be any point set in $R=[a_{1},a_{2}]\times[b_{1},b_{2}]$. There exists
a deterministic algorithm of computing an $\epsilon$-net of size at most
$8/\epsilon$ for $P$ and all three-sided axis-aligned rectangles with respect
to $R$. The running time of the algorithm is $O(|P|\log|P|)$.

We obtain the deterministic algorithm of constructing a $O(\log n/|P|)$-net of
a constant fraction size for any point set $P$ and axis-aligned rectangles in
near linear time. For simplicity, we assume that $|P|$ is a power of two in
the lemma below, but it is not essential.

###### Lemma 12

Let $P$ be any set of points in $[a_{1},a_{2}]\times[b_{1},b_{2}]$, and $N$ be
any upper bound of $|P|$. There exists a deterministic algorithm
$\mathsf{NetFind}(N,P)$ which constructs a $(32\log N/|P|)$-net of size at
most $|P|\log|P|/(2\log N)$ for $P$ and all axis-aligned rectangles in
$O(|P|\log|P|\log N)$ time.

###### Proof.

We first present the algorithm. It is based on the divide and conquer approach
as follows:

  1. 1.

If $|P|>4\log N$: find the vertical line $x=M$ bisecting $P$ into two equal-
size subsets $P_{0}$ and $P_{1}$ (with an arbitrary tie-breaking rule for the
points on $x=M$). Let $R_{0}=[a_{1},M]\times[b_{1},b_{2}]$ and
$R_{1}=[M,a_{2}]\times[b_{1},b_{2}]$. Then $\mathsf{NetFind}(N,P)$ outputs the
union of the following four subsets of $P$:

     * •

The outputs of $\mathsf{NetFind}(N,P_{0})$ and $\mathsf{NetFind}(N,P_{1})$.

     * •

The $(16\log N/|P_{i}|)$-nets obtained by the algorithm of Lemma 11 for
$P_{i}$ and all three-sided axis-aligned rectangles with respect to $R_{i}$,
for $i=0,1$.

  2. 2.

If $|P|\leq 4\log N$: output the empty set.

Let $P^{\prime}$ be the output in the run of $\mathsf{NetFind}(N,P)$. The
proof is based on the induction on the size of $P$.

(Basis) $|P|\leq 4\log N$ holds: Then the case 2 of the algorithm applies. The
output size is trivially bounded by $|P|\log|P|/(2\log N)\geq 0$. Since
$|P|\leq 4\log N$ holds, there is no axis-aligned rectangle containing more
than $32\log N$ points. Hence the constructed output (i.e., the empty set) is
a $(32\log N/|P|)$-net.

(Inductive Step): Let $P$ be the set of points such that $|P|>4\log N$ holds.
Suppose as the induction hypothesis $\mathsf{NetFind}(N,Q)$ correctly outputs
a $(32\log N/|Q|)$-net of size at most $|Q|/(2(\log(N/|Q|))$ for any
$Q\subseteq P$ such that $|Q|=|P|/2$ holds. Consider any axis-aligned
rectangle $X$ such that $|R\cap P|\geq 32\log N$ holds. We show that $X$
necessarily contains a point in $P^{\prime}$. By the induction hypothesis,
both $\mathsf{NetFind}(N,P_{0})$ and $\mathsf{NetFind}(N,P_{1})$ correctly
computes a $(32\log N/|P_{0}|)$-net and a $(32\log N/|P_{1}|)$-net. Hence if
$X$ is contained either $R_{0}$ or $R_{1}$, $X$ necessarily contains a point
in $P^{\prime}$. If $X$ intersects $x=M$, $X\cap R_{0}$ and $X\cap R_{1}$
become the three-sided axis-aligned rectangles with respect to $R_{0}$, and
$R_{1}$, one of which contains $16\log N$ points in $P$. Assume $X\cap R_{0}$
is such a side wlog. Since $P^{\prime}$ necessarily contains a $(16\log
N/|P_{i}|)$-net of $P$ and three-sided axis-aligned rectangles with respect to
$R_{0}$, $X\cap R_{0}$ intersects $P^{\prime}$. That is, $R$ intersects
$P^{\prime}$. Let $Q_{i}$ be the output of $\mathsf{NetFind}(N,P_{i})$, and
$Q^{\prime}_{i}$ be the constructed $(16\log N/|P_{i}|)$-net for $P_{i}$ and
all three-sided axis-aligned rectangles with respect to $R_{i}$ ($i=0,1$).
Then $|P^{\prime}|\leq|Q_{0}|+|Q_{1}|+|Q^{\prime}_{0}|+|Q^{\prime}_{1}|$
holds. By the induction hypothesis, we have
$|Q_{i}|\leq((|P|/2)\log(|P|/2))/(2\log N)$ for $i=0,1$. By Lemma 11,
$Q^{\prime}_{i}\leq|P|/(4\log N)$ holds for $i=0,1$. Then the size of
$P^{\prime}$ is bounded as follows:

$\displaystyle|P^{\prime}|$ $\displaystyle\leq
2\cdot\frac{\frac{|P|}{2}\log\frac{|P|}{2}}{2\log N}+2\cdot\frac{|P|}{4\log
N}$ $\displaystyle\leq\frac{|P|(\log|P|-1)}{2\log N}+\frac{|P|}{2\log N}$
$\displaystyle\leq\frac{|P|\log|P|}{2\log N}.$

It is easy to bound the running time because the total running time of all
recursive calls at the same depth is bounded by $O(|P|\log N)$. The lemma is
proved. ∎

Lemma 4 is obviously obtained from Lemma 10 and Lemma 12. We finally show the
main lemma of this section.

###### Lemma 0

There exists two deterministic algorithms respectively constructing a
$(\mathcal{S}_{f,T},k)$-good hierarchy with the following performance
guarantees:

  * •

$k=O(f^{2}\log n)$ and the construction time is $\tilde{O}(m)$.

  * •

$k=O(f^{2}\log\log n)$ and the construction time is $\mathrm{poly}(m)$.

###### Proof.

We only show that first construction, but the second construction is proved in
the same way. Consider the construction of $E_{i+1}$ from $E_{i}$. The
algorithm first maps all the edges in $E_{i}$ into the space $[1,2n-2]^{2}$.
Applying the algorithm of Lemma 12 to $E_{i}$ with $P=E_{i}$ and $N=|E_{i}|$,
we obtain an $(32\log|E_{i}|/|E_{i}|)$-net $E_{i+1}$ of a constant fraction
size for $E_{i}$ and all axis-aligned rectangles. As mentioned in Section 4.3,
$E_{i+1}$ works as a $(32(2f+1)^{2}\log n/|E_{i}|)$-net for $\mathcal{H}_{2f}$
and thus it satisfies the condition of $(\mathcal{S}_{f,T},32(2f+1)^{2}\log
n)$-good edge hierarchy. Since $E_{i+1}$ is a subset of $E_{i}$ with a
constant fraction size, the depth $h$ of hierarchy is bounded by $O(\log n)$.
The construction time of $E_{i+1}$ from $E_{i}$ follows the running time of
the algorithm of Lemma 12, i.e., it takes $\tilde{O}(m)$ time. Hence the total
running time is $\tilde{O}(m)$. ∎

##  Appendix C Fast Query Processing

We construct a refined query processing algorithm for our tree edge $f$-FTC
labeling scheme. Let $G^{\ast}=G-E_{T}$ for short. Throughout this section, we
assume that the tree edge $f$-FTC labeling scheme is implemented with any
adaptive $\mathcal{S}_{f,T}$-outdetect labeling scheme
$(L^{\mathsf{out}}_{G^{\ast}},D^{\mathsf{out}})$ of $\tilde{O}(f^{b})$-bit
label size which admits $\tilde{O}(|\partial_{T}(S)|^{c})$ decoding time for a
given query $S\subseteq V_{G^{\ast}}$, as explained in Section 6. Similarly as
the original one, the refined algorithm also iteratively merges the vertices
of the component graph $T/\mathcal{C}(F)$. It manages a collection
$\mathcal{X}$ of disjoint subsets of $\mathcal{C}(F)$ throughout the
procedure. A subset $S\subseteq\mathcal{C}(F)$ in $\mathcal{X}$ is called a
_component fragment_ (note that $S$ is not a subset of $V_{G}$). For any
component fragment $S\subseteq\mathcal{C}(F)$, we define $V(S)\subseteq V_{G}$
as $V(S)=\bigcup_{C\in S}C$. As a loop invariant, the algorithm guarantees
that $V(S)$ for any component fragment $S\in\mathcal{X}$ induces a connected
subgraph of $G-F$. Each component fragment $S\subseteq\mathcal{C}(F)$ is
stored as the triple
$(S,\partial_{T}(V(S)),L^{\mathsf{out}}_{G^{\ast}}(V(S)))$ in $\mathcal{X}$.
We denote this triple associated with $S\subseteq\mathcal{C}(F)$ by $\tau(S)$.
The whole structure of the algorithm is stated below:

  1. 1.

Initially, we set $\mathcal{X}=\\{\tau(\\{C\\})\mid C\in\mathcal{C}(F)\\}$.

  2. 2.

In each iteration, we pick up $\tau(S)$ such that $|\partial_{T}(V(S))|$ is
the smallest, and find an outgoing edge of $S$ by decoding
$L^{\mathsf{out}}_{G^{\ast}}(V(S))$, which is obtained from
$L^{\mathsf{out}}_{G^{\ast},K}(V(S))$ stored in $\tau(S)$.

  3. 3.

If no outgoing edge of $S$ is found, we remove $\tau(S)$ from $\mathcal{X}$
and go to the next iteration. Otherwise, let $S^{\prime}$ be the component
fragment the outgoing edge from $S$ reaches.

  4. 4.

If $S$ and $S^{\prime}$ contains $s$ and $t$ respectively, the procedure
terminates with returning true. Otherwise, the algorithm deletes $\tau(S)$ and
$\tau(S^{\prime})$ from $\mathcal{X}$, and newly insert the entry of
$\tau(S^{\prime\prime})$ for $S^{\prime\prime}=S\cup S^{\prime}$. The entry
$\tau(S^{\prime\prime})$ is computed as
$\tau(S^{\prime\prime})=(S^{\prime\prime},(\partial_{T}(V(S))\cup\partial_{T}(V(S^{\prime})))\setminus(\partial_{T}(V(S))\cap\partial_{T}(V(S^{\prime}))),L^{\mathsf{out}}_{G^{\ast}}(V(S))+L^{\mathsf{out}}_{G^{\ast}}(V(S^{\prime})))$.
After the insertion, the algorithm proceeds to the next iteration unless
$|\mathcal{X}|=1$ holds. If $|\mathcal{X}|=1$ holds, the algorithm terminates
with returning false (this case occurs only when the component fragment
containing $s$ or $t$ is discarded).

To implement the algorithm above efficiently, we manage $\mathcal{X}$ by the
heap which supports $O(\log|\mathcal{X}|)$-time insert, delete, and search of
the element having the minimum cutset. Each cutset associated with an element
in $\mathcal{X}$ is stored as the bit vector of length $|F|$ and the
additional integer value representing the size of the stored cutset. This data
structure obviously supports union and intersection in $O(|F|)$ time, as well
as getting the cutset size in $O(1)$ time. Each fragment $S$ associated with a
triple in $\mathcal{X}$ is managed by any disjoint-set data structure (e.g.,
union-find) over $\mathcal{C}(F)$. Combining this structure with Proposition
3, one can determine the fragment $S\in\mathcal{X}$ containing a given vertex
$u\in V_{G}$ from $L^{\mathsf{anc}}_{T}(u)$ in $O(\log|F|)$ time (i.e.,
identify $C\in\mathcal{C}(F)$ containing $u$ first, and then identify
$S\in\mathcal{X}$ containing $C$). With support of all the data structures
above, we can implement one iteration of the refined procedure in
$\tilde{O}(|F|^{b}+|\partial_{T}(V(S))|^{c})$ time. The initialization of
$\mathcal{X}$ is implemented in $\tilde{O}(|F|^{b+1})$ time. We show that the
refined algorithm runs in $\tilde{O}(|F|^{c})$ time in total.

###### Lemma 0

Assume that there exists a $\mathcal{S}_{f,T}$-outdetect labeling scheme of
label size $\alpha=\tilde{O}(f^{b})$ and decoding time
$\beta=\tilde{O}(f^{c})$. Then there exists a $f$-FTC labeling scheme of
$O(\alpha+\log n)$-bit label size and $\tilde{O}(|F|^{b+1}+|F|^{c})$ decoding
time. The resultant $f$-FTC labeling scheme is deterministic if the
corresponding $\mathcal{S}_{f,T}$-outdetect labeling scheme is deterministic.

###### Proof.

Consider the refined query processing algorithm above. We denote by
$\mathcal{X}_{i}$ the set $\mathcal{X}$ at the beginning of the $i$-th
iteration, and let
$\mathcal{Y}_{i}=\\{S\mid(S,\cdot,\cdot)\in\mathcal{X}_{i}\\}$. Since
$\mathcal{Y}_{i}$ is a disjoint collection of component fragments and each
$S\in\mathcal{Y}_{i}$ satisfies $\partial_{T}(V(S))\subseteq F$, we have
$\sum_{S\in\mathcal{Y}_{i}}|\partial_{T}(S)|\leq 2|F|$. Let
$S_{1},S_{2}\dots,S_{x}$ be the component fragments chosen in each iteration
($x\leq|F|$). Since the algorithm chooses $S_{i}$ minimizing
$|\partial_{T}(V(S_{i}))|$, we have $|\partial_{T}(V(S_{i}))|\leq
2|F|/|\mathcal{Y}_{i}|$. As discussed in this section, the detection of an
outgoing edge of $S_{i}$ takes $\tilde{O}(|\partial_{T}(V(S_{i}))|^{c})$ time.
Since at least one component in $\mathcal{Y}_{i}$ is merged or discarded in
the $i$-th iteration, we have $|\mathcal{Y}_{i+1}|\leq|\mathcal{Y}_{i}|-1$.
The computation time excluding that for the outgoing edge detection is
$O(|F|^{b}\log n)$ per one iteration. The total running time is bounded as
follows:

$\displaystyle\sum_{1\leq
i\leq|F|}\tilde{O}\left(\left(\frac{|F|}{i}\right)^{c}+|F|^{b}\right)$
$\displaystyle\leq\tilde{O}(|F|^{c})\cdot\sum_{1\leq
i\leq|F|}\frac{1}{i^{c}}+\tilde{O}(|F|^{b+1})$
$\displaystyle\leq\tilde{O}(|F|^{c}+|F|^{b+1}).$

∎

##  Appendix D Randomized Construction of Edge Set Hierarchy

Comparing the quality of labeling schemes with the label size, decoding time,
and construction time, our deterministic construction is competitive but
certainly worse than the known randomized scheme. However, most of high costs
incurred by our construction is derived from the construction of edge set
hierarchies. As mentioned in Section 4.3, a simple edge sub-sampling strategy
suffices to construct good hierarchies.

###### Proposition 5

Let $E_{G^{\ast}}=E_{0}\supseteq E_{1}\supseteq E_{2}\supseteq,\dots,\supseteq
E_{h}=\emptyset$ be the edge set hierarchy such that $E_{i+1}$ is obtained by
sampling each edge in $E_{i}$ independently with probability $1/2$. Then with
probability $1-1/n^{O(1)}$, this hierarchy is $(\mathcal{S}_{f,T},5f\log
n)$-good.

###### Proof.

Consider the construction of $E_{i+1}$ from $E_{i}$. If $|E_{i}|\leq 5f\log
n$, we decide $E_{i+1}=\emptyset$. Otherwise, sample each edge in $E_{i}$ with
probability $1/2$. We show that with high probability,
$|\partial_{E_{i+1}}(S)|>0$ holds for any $S\in\mathcal{S}_{f,T}$ satisfying
$|\partial_{E_{i}}(S)|>5f\log n$. The probability that no edge in
$\partial_{E_{i}}(S)$ is added to $E_{i+1}$ is at most $(1/2)^{5f\log
n}=1/n^{5f}$. Since the cardinality of $\mathcal{S}_{f,T}$ is bounded by
$\binom{|E_{T}|}{f}=O(n^{f})$, by the union bound argument, we conclude that
$|\partial_{E_{i+1}}(S)|>0$ holds for any $S\in\mathcal{S}_{f,T}$ satisfying
$|\partial_{E_{i}}(S)|>5f\log n$ with probability $1-O(1/n^{5})$. This
statement holds for all possible $c$ with probability at least $1-O(1/n^{5})$.
That is, the probability that $E_{i+1}$ does not satisfies the second
condition of Definition 1 is $O(1/n^{4})$. The first condition is satisfied
with high probability because one can show $|E_{i+1}|\leq 3|E_{i}|/4$ with
probability $1-O(1/n^{2})$ by the straightforward application of Chernoff
bound. Applying the union bound again on the failing events of the first and
second conditions for all $i$, we obtain the proposition. ∎

##  Appendix E Adaptive Decoding of Deterministic
$\mathcal{S}_{f,T}$-outdetect labeling scheme based on the Reed-Solomon Code

In this appendix, we show that our $\mathcal{S}_{f,T}$-outdetect labeling
scheme attains the adaptiveness without any modification or transformation.
The key idea is a nice property of Reed-Solomon Code: We define
$L^{\mathsf{RS}(k)}_{H,k^{\prime}}$ for $k^{\prime}\leq k$ as the labeling
function which assign $v\in V_{H}$ with the prefix of
$L^{\mathsf{RS}(k)}_{H}(v)$ up to the $k^{\prime}$-th element. Then the
following proposition holds:

###### Proposition 6

For any $k^{\prime}\leq k$,
$L^{\mathsf{RS}(k)}_{H,k^{\prime}}=L^{\mathsf{RS}(k^{\prime})}_{H}$ holds.

###### Proof.

The proof trivially follows the definition of the parity check matrix
$C_{2k}$. Let $c_{ij}$ be the $(i,j)$-element of $C_{2k}$ ($0\leq
i\leq|\mathcal{E}|,0\leq j\leq 2k-1$) and $\omega$ be a primitive element of
$\mathbb{F}$. Then the each element of $C_{2k}$ is defined as
$c_{ij}=\omega^{ij}$. That is, the submatrix formed by the first $2k^{\prime}$
columns of $C_{2k}$ is is equal to $C_{2k^{\prime}}$. ∎

Intuitively, the proposition above implies that the $O(k^{\prime}\log n)$-bit
prefixes of the labels assigned by our $k$-threshold outdetect labeling scheme
also work as the labels of the $k^{\prime}$-threshold outdetect labeling
scheme. It is also possible to make the sparsification hierarchy adaptive
because our construction does not use the upper bound $f$ at all, i.e., the
construction is universal for every $f$: We explained in the previous section
that $E_{i+1}$ is constructed in the way that it becomes the hitting set of
$\mathcal{Z}_{i,f,cf^{2}\log n}$ (where $c$ is a hidden constant). In reality,
it also becomes the hitting set of
$\mathcal{Z}_{i,f^{\prime},c(f^{\prime})^{2}}$ for any $f^{\prime}>0$. Hence
it is guaranteed that for any $S\in\mathcal{S}_{|\partial_{T}(S)|,T}$ there
exists an index $i$ such that $0<|\partial_{G_{i}}(S)|\leq
c|\partial_{T}(S)|^{2}\log n$ holds (in the deterministic case).

## References

  * ACG [12] Ittai Abraham, Shiri Chechik, and Cyril Gavoille.  Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.  In Proc. of the 44th Annual ACM Symposium on Theory of Computing (STOC), page 1199â1218, 2012.
  * ACGP [16] Ittai Abraham, Shiri Chechik, Cyril Gavoille, and David Peleg.  Forbidden-set distance labels for graphs of bounded doubling dimension.  ACM Transactions on Algorithms, 12(2), 2016.
  * [3] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Analyzing graph structure via linear measurements.  In Proc. of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 459–467. SIAM, 2012.
  * [4] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.  Graph sketches: Sparsification, spanners, and subgraphs.  In Proc. of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), page 5â14, 2012.
  * BCG+ [18] Davide Bilò, Keerti Choudhary, Luciano Gualà, Stefano Leucci, Merav Parter, and Guido Proietti.  Efficient Oracles and Routing Schemes for Replacement Paths.  In Proc. of 35th Symposium on Theoretical Aspects of Computer Science (STACS), volume 96 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:15, 2018.
  * BCG+ [21] Aviv Bar-Natan, Panagiotis Charalampopoulos, Pawel Gawrychowski, Shay Mozes, and Oren Weimann.  Fault-tolerant distance labeling for planar graphs.  In In Proc. of International Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 12810 of Lecture Notes in Computer Science, pages 315–333, 2021.
  * BGLP [16] Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti.  Compact and fast sensitivity oracles for single-source distances.  In Piotr Sankowski and Christos D. Zaroliagis, editors, Proc. of 24th Annual European Symposium on Algorithms (ESA), volume 57 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:14, 2016.
  * BK [09] Aaron Bernstein and David Karger.  A nearly optimal oracle for avoiding failed vertices and edges.  In Proc. of the 41st Annual ACM Symposium on Theory of Computing (STOC), page 101â110, 2009.
  * BK [13] Surender Baswana and Neelesh Khanna.  Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs.  Algorithmica, 66(1):18–50, 2013.
  * CCFK [17] Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan.  $(1+\epsilon)$-approximate $f$-sensitive distance oracles.  In Proc. of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1479–1496, 2017.
  * CGL+ [20] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak.  A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond.  In 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 1158–1167. IEEE, 2020.
  * Che [11] Shiri Chechik.  Fault-tolerant compact routing schemes for general graphs.  In 38th International Colloquium on Automata, Languages, and Programming, (ICALP), pages 101–112, 2011.
  * CLPR [12] Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty.  $f$-sensitivity distance oracles and routing schemes.  Algorithmica, 63(4):861â882, 2012.
  * CM [96] Bernard Chazelle and Jiří Matoušek.  On linear-time deterministic algorithms for optimization problems in fixed dimension.  Journal of Algorithms, 21(3):579–597, 1996.
  * CT [07] Bruno Courcelle and Andrew Twigg.  Compact forbidden-set routing.  In Proceedings of the 24th Annual Conference on Theoretical Aspects of Computer Science, STACS’07, page 37â48, 2007.
  * CT [10] Bruno Courcelle and Andrew Twigg.  Constrained-path labellings on graphs of bounded clique-width.  Theory of Computing Systems, 47(2), 2010.
  * DORS [08] Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, and Adam Smith.  Fuzzy extractors: How to generate strong keys from biometrics and other noisy data.  SIAM Journal on Computing, 38(1):97–139, 2008.
  * DP [09] Ran Duan and Seth Pettie.  Dual-failure distance and connectivity oracles.  In Proc. of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 506â515, 2009.
  * DP [10] Ran Duan and Seth Pettie.  Connectivity oracles for failure prone graphs.  In Proc. of the 42nd ACM Symposium on Theory of Computing (STOC), page 465â474, 2010.
  * DP [20] Ran Duan and Seth Pettie.  Connectivity oracles for graphs subject to vertex failures.  SIAM Journal on Computing, 49(6):1363–1396, 2020.
  * DP [21] Michal Dory and Merav Parter.  Fault-tolerant labeling and compact routing schemes.  In Proc. of the 2021 ACM Symposium on Principles of Distributed Computing (PODC), page 445â455, 2021.
  * DT [02] Camil Demetrescu and Mikkel Thorup.  Oracles for distances avoiding a link-failure.  In Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page 838â843, 2002.
  * FKMS [07] Joan Feigenbaum, David R. Karger, Vahab S. Mirrokni, and Rahul Sami.  Subjective-cost policy routing.  Theoretical Computer Science, 378(2):175–189, 2007.
  * GK [18] Mohsen Ghaffari and Fabian Kuhn.  Distributed MST and broadcast with fewer messages, and faster gossiping.  In Proc. of 32nd International Symposium on Distributed Computing (DISC), volume 121 of LIPIcs, pages 30:1–30:12, 2018.
  * GKKT [15] 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.
  * GP [16] Mohsen Ghaffari and Merav Parter.  Mst in log-star rounds of congested clique.  In Proc. of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), page 19â28, 2016.
  * GP [18] Robert Gmyr and Gopal Pandurangan.  Time-message trade-offs in distributed algorithms.  In Proc. of 32nd International Symposium on Distributed Computing (DISC), volume 121 of LIPIcs, pages 32:1–32:18, 2018.
  * GR [21] Yong Gu and Hanlin Ren.  Constructing a distance sensitivity oracle in $o(n^{2.5794}m)$ time.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, (ICALP), volume 198 of LIPIcs, pages 76:1–76:20, 2021.
  * GW [19] Fabrizio Grandoni and Virginia Vassilevska Williams.  Faster replacement paths and distance sensitivity oracles.  ACM Transactions on Algorithms, 16(1), 2019.
  * HdLT [01] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup.  Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity.  Journal of the ACM, 48(4):723â760, 2001.
  * HK [99] Monika R. Henzinger and Valerie King.  Randomized fully dynamic graph algorithms with polylogarithmic time per operation.  Journal of the ACM, 46(4):502â516, 1999.
  * HPP+ [15] James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato.  Toward optimal bounds in the congested clique: Graph connectivity and mst.  In Proc. of the 2015 ACM Symposium on Principles of Distributed Computing (PODC), page 91â100, 2015.
  * HW [87] David Haussler and Emo Welzl.  epsilon-nets and simplex range queries.  Discrete Computational Geometry, 2:127–151, 1987.
  * JN [18] Tomasz Jurdzinski and Krzysztof Nowicki.  MST in $O(1)$ rounds of the congested clique.  In Proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2620–2632, 2018.
  * KG [10] Janardhan Kulkarni and Sathish Govindarajan.  New epsilon-net constructions.  In 22nd Annual Canadian Conference on Computational Geometry (CCCG), pages 159–162, 2010.
  * KKM [13] Bruce M. Kapron, Valerie King, and Ben Mountjoy.  Dynamic graph connectivity in polylogarithmic worst case time.  In Proc. of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1131–1142, 2013.
  * KKT [15] Valerie King, Shay Kutten, and Mikkel Thorup.  Construction and impromptu repair of an mst in a distributed network with $o(m)$ communication.  In Proc. of the ACM Symposium on Principles of Distributed Computing (PODC), page 71â80, 2015.
  * KLM+ [14] Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford.  Single pass spectral sparsification in dynamic streams.  In Proc. of 55th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 561–570, 2014.
  * KNR [92] Sampath Kannan, Moni Naor, and Steven Rudich.  Implicit representation of graphs.  SIAM Journal on Discrete Mathematics, 5(4):596–603, 1992.
  * KW [14] Michael Kapralov and David Woodruff.  Spanners and sparsifiers in dynamic streams.  In Proc. of the 2014 ACM Symposium on Principles of Distributed Computing (PODC), page 272â281, 2014.
  * Mat [96] Jiří Matoušek.  Derandomization in computational geometry.  Journal of Algorithms, 20(3):545–580, 1996.
  * MDG [18] Nabil H. Mustafa, Kunal Dutta, and Arijit Ghosh.  A simple proof of optimal epsilon nets.  Combinatorica, 38(5):1269â1277, 2018.
  * MK [21] Ali Mashreghi and Valerie King.  Broadcast and minimum spanning tree with $o(m)$ messages in the asynchronous CONGEST model.  Distributed Computing, 34(4):283–299, 2021.
  * PD [06] Mihai Patrascu and Erik D. Demaine.  Logarithmic lower bounds in the cell-probe model.  SIAM Journal on Computing, 35(4):932–963, 2006.
  * [45] Merav Parter and Asaf Petruschka.  Near-optimal distributed computation of small vertex cuts.  In 36th International Symposium on Distributed Computing (DISC), volume 246, pages 31:1–31:21, 2022.
  * [46] Merav Parter and Asaf Petruschka.  Õptimal Dual Vertex Failure Connectivity Labels.  In 36th International Symposium on Distributed Computing (DISC 2022), pages 32:1–32:19, 2022.
  * PT [07] M. Patrascu and M. Thorup.  Planning for fast connectivity updates.  In Proc. of 48th Annual IEEE Symposium on Foundations of Computer Science, pages 263–271, 2007.
  * PT [11] David Pritchard and Ramakrishna Thurimella.  Fast computation of small cuts via cycle space sampling.  ACM Transactions on Algorithms, 7(4), 2011.
  * Raj [12] Varun Rajan.  Space efficient edge-fault tolerant routing.  In Deepak D’Souza, Telikepalli Kavitha, and Jaikumar Radhakrishnan, editors, Proc. of IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, (FSTTCS), volume 18 of Leibniz International Proceedings in Informatics (LIPIcs), pages 350–361, 2012\.
  * Tho [00] Mikkel Thorup.  Near-optimal fully-dynamic graph connectivity.  In The 32nd Annual ACM Symposium on Theory of Computing (STOC), page 343â350, 2000.
  * [51] Christian Wulff-Nilsen.  Faster deterministic fully-dynamic graph connectivity.  In The 2013 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1757–1769.