# Near-Optimal Deterministic Vertex-Failure Connectivity Oracles

Yaowei Long
University of Michigan  Thatchaphol Saranurak
University of Michigan

###### Abstract

We revisit the _vertex-failure connectivity oracle_ problem [DP10, BPWN12,
DP20]. This is one of the most basic graph data structure problems under
_vertex updates_ , yet its complexity is still not well-understood. We
essentially settle the complexity of this problem by showing a new data
structure whose space, preprocessing time, update time, and query time are
simultaneously optimal up to sub-polynomial factors assuming popular
conjectures. Moreover, the data structure is deterministic.

More precisely, for any integer $d_{\star}$, the data structure preprocesses a
graph $G$ with $n$ vertices and $m$ edges in $\hat{O}(md_{\star})$ time and
uses $\tilde{O}(\min\\{m,nd_{\star}\\})$ space. Then, given the vertex set $D$
to be deleted where $|D|=d\leq d_{\star}$, it takes $\hat{O}(d^{2})$ updates
time. Finally, given any vertex pair $(u,v)$, it checks if $u$ and $v$ are
connected in $G\setminus D$ in $O(d)$ time. This improves the previously best
deterministic algorithm by Duan and Pettie [DP20] in both space and update
time by a factor of $d$. It also significantly speeds up the
$\Omega(\min\\{mn,n^{\omega}\\})$ preprocessing time of all known (even
randomized) algorithms with update time at most $\tilde{O}(d^{5})$.

###### Contents

  1. 1 Introduction
  2. 2 Technical Overview
    1. 2.1 Low Degree Hierarchy via Vertex Expander Decomposition
    2. 2.2 Optimal Deterministic Oracles
  3. 3 Preliminaries
  4. 4 Weighted Vertex Expander Decomposition
    1. 4.1 The Cut-Matching Game
    2. 4.2 Most-Balanced Sparse Vertex Cut
  5. 5 The Low Degree Hierarchy
    1. 5.1 Repeated Vertex Expander Decomposition
    2. 5.2 Construction
  6. 6 The Affiliated Structures
    1. 6.1 The Abstract Graph $H$ for a Failure Set $D$
    2. 6.2 Overview
    3. 6.3 The Euler Tour Order and the 2D Range Counting Structure
    4. 6.4 Artificial Edges
  7. 7 Update and Query Algorithms
    1. 7.1 The Update Algorithm
    2. 7.2 Solving Connectivity of Intervals: Proof of Lemma 7.4
    3. 7.3 The Query Algorithm
  8. 8 Conditional Lower Bounds
  9. 9 Open Problems
  10. A Omitted Proof
    1. A.1 Proof of Theorem 4.3 and Corollary 4.4
    2. A.2 Proof of Lemma 4.13
    3. A.3 Proof of Lemma 4.14 and Corollary 4.15
    4. A.4 Proof of Lemma 4.6
    5. A.5 Proof of Lemma 6.3
  11. B Deterministic Approximate Vertex-Capacitated Max Flow
  12. C Expander Decomposition for Hypergraphs

##  1 Introduction

We revisit the _vertex-failure connectivity oracle_ problem [DP10, BPWN12,
DP20]. This is one of the most basic graph data structure problems under
_vertex updates_ , yet its complexity is still not well-understood. In this
paper, we essentially settle the complexity of this problem by showing a new
data structure whose space, preprocessing time, update time, and query time
are simultaneously optimal up to sub-polynomial factors assuming popular
conjectures. Moreover, the data structure is deterministic.

More precisely, in the vertex-failure connectivity oracle problem, there are
three phases. First, we preprocess an undirected graph $G=(V,E)$ with $n$
vertices and $m$ edges and an integer $d_{\star}$. Second, given a vertex set
$D\subset V$ of size $|D|=d\leq d_{\star}$, we update the data structure.
Finally, given a vertex pair $(u,v)$, we return whether $u$ and $v$ are
connected in the updated graph $G\setminus D$. The _preprocessing_ ,_update,_
and _query time_ are the time used by the data structured in the first,
second, and third phases respectively. Put it another way, this problem is
just the well-known decremental connectivity problem when all vertex deletions
in given in one batch, instead of an online sequence of updates.

To see the context, we also mention its sister problem, the _edge_ -failure
connectivity oracle problem, where we are given $d$ edges to be deleted
instead of vertices. Since 1997, Pastrascu and Thorup [PT07] already showed a
near-optimal deterministic edge-failure oracle, except that it has large
preprocessing time. This is later improved to a near-optimal oracle with
$\tilde{O}(m)$ space111The algorithm uses $\tilde{O}(n)$ space outside storing
the graph. In [DP20], they claimed $\tilde{O}(n)$ total space by assuming that
$D\subseteq E$ and each edge in $D$ is specified by its two endpoints. Note
that, in general, $\Omega(m)$ space is unavoidable as the oracles can be used
to reconstruct any connected graph: we can query if $(u,v)\in E$, by deleting
$\binom{V}{2}\setminus(u,v)$ and querying if $u$ and $v$ are connected.,
$\tilde{O}(m)$ preprocessing, $\tilde{O}(d)$ update, and $O(\log\log n)$ query
time using the linear sketching techniques (see Threoem 7.9 of [DP20] and also
[KKM13, GKKT15]).222Throughout the paper, we use $\tilde{O}(\cdot)$ to hide a
$\mathrm{polylog}(n)$ factor, use $\hat{O}(\cdot)$ to hide a $n^{o(1)}$ factor
and use $\bar{O}(\cdot)$ to hide a $\mathrm{polyloglog}(n)$ factor.

The state of the art for vertex-failure connectivity oracles is much worse.
The high-level reason why vertex failures are more challenging is because,
while $d$ edge deletions cause at most $d$ new connected components, just a
single vertex deletion may create a lot of new connect components. For very
small $d_{\star}\leq 2$, classical graph decompositions such that block trees
and SQRT trees yield optimal vertex-failure oracles. When $d_{\star}=3$, the
data structure by Kanevsky et al. [KTDBC91] implies a near-optimal oracle with
$O(n)$ space, $\tilde{O}(m)$ preprocessing, $O(1)$ update and query time. It
was until 2010 when Duan and Pettie [DP10] gave the first solution for general
$d_{\star}$ by showing a deterministic data structure with
$\tilde{O}(md_{\star}^{1-\frac{2}{c}}n^{\frac{1}{c}-\frac{1}{c\log(2d_{\star})}})$
space and preprocessing time, $\tilde{O}(d^{2c+4})$ update and $O(d)$ query
time. Later in 2017, they [DP20] showed two improved algorithms: (1) a
deterministic data structure with $\tilde{O}(md_{\star})$ space,
$\tilde{O}(mn)$ preprocessing, $\tilde{O}(d^{3})$ update, and $O(d)$ query
time, and (2) a randomized Monte Carlo data structure with $\tilde{O}(m)$
space, $\tilde{O}(mn)$ preprocessing, $\tilde{O}(d^{2})$ update, and $O(d)$
query time. More recently, oracles whose update and query time depend only on
$d_{\star}$ or $d$ were shown [vdBS19, PSS+21], but the bounds are
significantly slower than the ones in [DP20] when $\mathrm{polylog}(n)$
factors are ignored.

Given the big discrepancy between the edge-failure and vertex-failure cases in
all time bounds, a natural question is whether we can match them.
Unfortunately, the conditional lower bounds [HKNS15] show that query time must
be $\hat{\Omega}(d)$ as long as the algorithm has $\mathrm{poly}(n)$
preprocessing and $\mathrm{poly}(dn^{o(1)})$ update time. This separates the
vertex case from the edge case. The next question is then

_What is the right complexity for vertex-failure connectivity oracles_?

Before our paper, the answer of this question was not well-understood. For
example, three questions are posted by Duan and Pettie [DP20] where they wrote
_“the following open problems are quite challenging”._ The first question is
about improving preprocessing time. Second, can we have both $\tilde{O}(d)$
update and query time? Third, is there a deterministic data structure with
$\tilde{O}(m)$ space? We resolve all these questions in this paper. In fact,
we essentially settle the complexity of all parameters of vertex-failure
connectivity oracles up to sub-polynomial factors assuming popular
conjectures.__

Our near-optimal deterministic oracle is stated below.

######  Theorem 1.1.

There exists a deterministic vertex failure connectivity oracle that uses
$O(m\log^{*}n)$ space, $\hat{O}(m)+\tilde{O}(md_{\star})$ preprocessing time,
$\hat{O}(d^{2})$ update time, and $O(d)$ query time.

All the $m$ factors can be replaced by $\bar{m}=\min\\{m,n(d_{\star}+1)\\}$ by
using the standard sparsification algorithm by Nagamochi and Ibaraki [NI92] to
first preprocess the graph in $O(m)$ time. (This also works for all known
oracles discussed above.) So the bounds can be improved to
$O(\bar{m}\log^{*}n)$ space333The $\log^{*}n$ factor in our space is
arbitrary. We can choose any growing function, which only affects the
$n^{o(1)}$ factor in the update time. and
$O(m)+\hat{O}(\bar{m})+\tilde{O}(\bar{m}d_{\star})$ preprocessing time. Also,
all the $n^{o(1)}$ factors in Theorem 1.1 come solely from the overhead factor
of the current deterministic vertex expander decomposition. It is believable
that there exists a vertex expander decomposition algorithm
$\mathrm{polylog}(n)$ overhead factor, which would automatically improve all
the $n^{o(1)}$ factors to $\mathrm{polylog}(n)$.444But this would increase our
space to $O(m\log^{2}n)$. See Theorem 7.1 for a detailed version of Theorem
1.1.

Comparing with known results (see Table 1), Theorem 1.1 improves the previous
best deterministic algorithm by [DP20] by a factor of $d$ in both space and
update time. It also significantly speeds up the
$\Omega(\min\\{mn,n^{\omega}\\})$ preprocessing time of all known (randomized)
algorithms with update time at most $\tilde{O}(d^{5})$. Lastly, our space
complexity also beats the state-of-the-art of $O(m\log^{6}n)$ in the
randomized oracle by [DP20].

Next, we state conditional lower bounds that is tight with Theorem 1.1.

######  Theorem 1.2.

Let $\mathcal{A}$ be any vertex-failure connectivity oracle with $t_{p}$
preprocessing time, $t_{u}$ update time, and $t_{q}$ query time bound.
Assuming popular conjectures, we have the following:

  1. 1.

$\mathcal{A}$ must take $\Omega(\min\\{m,nd_{\star}\\})$ space. (See [DP20])

  2. 2.

If $t_{p}=\mathrm{poly}(n)$, then $t_{u}+t_{q}=\hat{\Omega}(d^{2})$. (See
Theorem 8.6)

  3. 3.

If $t_{p}=\mathrm{poly}(n)$ and $t_{u}=\mathrm{poly}(dn^{o(1)})$, then
$t_{q}=\hat{\Omega}(d)$. (Corollary 3.12 of [HKNS15])

  4. 4.

If $t_{u},t_{q}=\mathrm{poly}(dn^{o(1)})$ and $\mathcal{A}$ is a combinatorial
algorithm555“Combinatorial” algorithms [AW14] are algorithms that do not use
fast matrix multiplication., then $t_{p}=\hat{\Omega}(md)$. (See Theorem 8.3)

The above result basically says that (1) we cannot improve the space bound,
(2) either update or query time must be at least $\hat{\Omega}(d^{2})$, (3)
query time must be at least $\hat{\Omega}(d)$, and (4) the preprocessing time
must be at least $\hat{\Omega}(md)$. This means that all parameters from
Theorem 1.1 are simultaneously tight up to sub-polynomial factors. Note,
however, that the preprocessing time is tight only for combinatorial
algorithms.

| Det./Rand. | Space | Preprocessing | Update | Query
---|---|---|---|---|---
Block trees, |  |  |  |  |
SQRT trees, and [KTDBC91] |  |  |  |  |
only when $d_{\star}\leq 3$ | Det. | $O(n)$ | $\tilde{O}(m)$ | $O(1)$ | $O(1)$
Duan & Pettie [DP10] for $c\geq 1$ | Det. | $\tilde{O}(\bar{m}d_{\star}^{1-\frac{2}{c}}n^{\frac{1}{c}-\frac{1}{c\log(2d_{\star})}})$ | linear in space | $\tilde{O}(d^{2c+4})$ | $O(d)$
Duan & Pettie [DP20] | Det. | $O(\bar{m}d_{\star}\log n)$ | $O(\bar{m}n\log n)$ | $O(d^{3}\log^{3}n)$ | $O(d)$
| Rand. | $O(\bar{m}\log^{6}n)$ | $O(\bar{m}n\log n)$ |  $\bar{O}(d^{2}\log^{3}n)$ w.h.p. | $O(d)$
van den Brand & Saranurak [vdBS19] | Rand. | $O(n^{2})$ | $O(n^{\omega})$ | $O(d^{\omega})$ | $O(d^{2})$
Pilipczuk et al. [PSS+21] | Det. | $\bar{m}2^{2^{O(d_{\star})}}$ | $\bar{m}n^{2}2^{2^{O(d_{\star})}}$ | $2^{2^{O(d_{\star})}}$ | $2^{2^{O(d_{\star})}}$
| Det. | $n^{2}\mathrm{poly}(d_{\star})$ | $\mathrm{poly}(n)2^{O(d_{\star}\log d_{\star})}$ | $\mathrm{poly}(d_{\star})$ | $\mathrm{poly}(d_{\star})$
This paper | Det. | $O(\bar{m}\log^{3}n)$ | $O(\bar{m}n\log n)$ | $\bar{O}(d^{2}\log^{3}n\log^{4}d)$ | $O(d)$
| Det. | $O(\bar{m}\log^{*}n)$ | $\hat{O}(m)+\tilde{O}(\bar{m}d_{\star})$ | $\hat{O}(d^{2})$ | $O(d)$
Table 1: Complexity of known vertex-failure connectivity oracles.
$\bar{m}=\min\\{m,n(d_{\star}+1)\\}$. The randomized algorithms are all Monte
Carlo. The $\log^{*}n$ factor in the space of the last result can be
substituted with any slowly growing function.

As a side result, we also study a related problem of _vertex-failure global
connectivity oracles._ This oracle is similar to a vertex-failure connectivity
oracle, except that in the second phase, after we are given $D\subset V$, we
only need to return if $G\setminus D$ is connected and there is no third
phase. Surprisingly, although this problem might seem easier because there is
only one binary number to maintain instead of $\binom{n}{2}$ possible queries,
we show that there is no oracle with reasonable update time for this problem.

######  Theorem 1.3.

Let $\mathcal{A}$ be a vertex-failure global connectivity oracle with
$\mathrm{poly}(n)$ preprocessing time. Assuming SETH, $\mathcal{A}$ must spend
$\hat{\Omega}(n)$ update time even when the deletion set $D$ has size
$|D|=n^{o(1)}$.

This is in stark contrast with the edge version; edge-failure connectivity
oracles of [PT07, KKM13, GKKT15] with $\tilde{O}(d)$ update time can also
answer global connectivity and even count the number of connected components.

##### Technical Highlights.

The technical novelty of this paper lies in the new oracle from Theorem 1.1
with two parts to be highlighted.

First, we give a $\hat{O}(m)$-time algorithm for computing the _low-degree
hierarchy_ of [DP20]. This step previously requires $O(mn\log n)$ time in the
preprocessing algorithm by Duan and Pettie [DP20] and it was their bottleneck.
This new algorithm then leads to faster preprocessing time. Actually, similar
hierarchies are the key structures behind most vertex-failure oracles (for the
connectivity problem [DP10] and for the shortest path problem [DGR21]) Our
construction is based on expander decomposition, which is very versatile, and
so we expect that the approach can be adapted to solves more problems under
vertex failures.

Towards our construction, we give the first almost-linear-time algorithm for
computing _vertex-expander decomposition_. Given that in the last decade
numerous fast graph algorithms are based on edge-expander decomposition (see
e.g. [ST04, KLOS14, RST14, NSWN17, CDK+21]), our fast vertex-expander
decomposition will likely very useful. To facilitate future applications, we
show a general decomposition that works even for general vertex weights and
demands. We even generalize the technique to obtain hypergraph-expander
decomposition. See 2.3 for the basic version, Theorem 4.3 for the weighted
version and Theorem C.3 for the hypergraph version.

Second, given a near-optimal low degree hierarchy, the main challenge is
designing an oracle with small space and update time based on it. There were
two previous solutions by Duan and Pettie [DP20]: (1) a randomized Monte-Carlo
near-optimal algorithm with $\tilde{O}(m)$ space and $\tilde{O}(d^{2})$ update
time, and (2) a deterministic algorithm with $\tilde{O}(md_{\star})$ space and
$\tilde{O}(d^{3})$ update time. We show how to achieve the best of both, near-
optimal and deterministic. The techniques we developed can be interpreted as a
deterministic repairable hypergraph-to-graph connectivity-sparsifer which
transforms a hypergraph to a graph with the same vertex set and almost
preserves pairwise connectivity in the vertex-failure setting. Actually, the
sparsifer is somewhat stronger because it preserves the connectivity of each
hyperedge individually. Thus we expect that this tool can have applications on
other vertex-failures problem. See the discussion at the very end of Section
2.2 for details.

##### Related work.

In [HN16], Henzinger and Neumann studied the same problem but in the _fully
dynamic_ setting where the updates can both turn-on or turn-off vertices (not
just turning-off as in our setting). Their result is a reduction to the
deletion-only version and so our new result implies an improved solution in
their setting too. When updates are given as an online sequence and fully
dynamic, this is exactly the well-studied _dynamic subgraph connectivity_
problem __[FI00, Cha06, CPR11, Dua10, DZ17] whose complexity was just settled
for combinatorial algorithms by the recent conditional lower bounds by [JX22].
In planar graphs, a near-optimal vertex-failure connectivity oracle was given
by Borradaile et al. [BPWN12].

##### Organization.

In Section 2 we give an overview of our techniques. We begin with some basic
notations in Section 3. In Section 4 we discuss the vertex expander
decomposition. In Section 5 we introduce the low degree hierarchy in [DP20]
and show an efficient construction algorithm. In Section 6 we augment the low
degree hierarchy with some affiliated structures, and we show the update and
query algorithm in Section 7. In Section 8, we show the conditional lower
bounds which almost match the upper bound from our oracle, and we discuss some
open problems in Section 9. Appendix A includes some proofs omitted in Section
4 and Section 6. In Appendix B we discuss a deterministic approximate vertex-
capacitated max flow algorithm. In Appendix C we extend the expander
decomposition results in Section 4 to hypergraphs.

##  2 Technical Overview

In this section, we give an overview of our main technical contribution, which
consists of two parts below.

###  2.1 Low Degree Hierarchy via Vertex Expander Decomposition

The _low degree hierarchy_ of Duan and Pettie [DP20] is the crucial underlying
structure of their oracle and also ours. We discuss it in Section 5 in
details. Although its definition is quite complicated (see Definition 5.1),
its purpose is easy to describe. Informally, this hierarchy allows us to
assume that the input graph is of the following format666This is informal
because this claim is slightly simplistic; the graph $G$ is a bit more
complicated (see Definition 6.1 of the abstract graph).:

  1. 1.

$G=(L,R,E)$ is a semi-bipartite graph (i.e. there is no edges between $R$),

  2. 2.

$L$ is spanned by a path $\tau$ and $\tau$ is given to us.

We will see why this graph can be useful in Section 2.2.

For now, we focus on constructing the hierarchy itself.

Duan and Pettie [DP20] showed that constructing the hierarchy reduces to
$O(\log n)$ calls to a decomposition related to Steiner forests. For any
terminal set $T\subseteq V$ in a graph $G$, we say that a forest $F\subseteq
E$ is a _$T$ -Steiner forest_ if, for every terminal pair $u,v\in T$, $u$ and
$v$ are connected in $F$ iff there are connected in $G$. The decomposition
says that, for any terminal set $T$, one can delete $|T|/2$ vertices from the
graph, so that the resulting graph contains a low-degree Steiner forest for
the remaining terminals. This is formalized as follows:

######  Lemma 2.1 (Low-degree Steiner Forest Decomposition [DP20]).

Let $G=(V,E)$ be a graph with terminal set $T\subseteq V$. There is a
$O(m|T|\log|T|)$-time algorithm that computes

  * •

a vertex set $X$ of size at most $|T|/2$, and

  * •

a $(T\setminus X)$-Steiner forest $F$ in $G\setminus X$ with maximum degree
$4$.

2.1 is based on the $(+1)$-additive-approximation algorithm for computing
minimum degree spanning trees by Furer and Raghavachari [FR94]. Calling 2.1
with $T=V$ leads to $\Omega(mn\log n)$ preprocessing time in [DP20].

Our key contribution is showing that, when the maximum degree of $F$ is
relaxed from $4$ to $n^{o(1)}$, the running time of 2.1 can be improved from
$O(m|T|\log|T|)$ to $\hat{O}(m)$. We completely bypass [FR94] and exploit
_vertex expanders_ instead.

Recall that a _vertex cut_ $(L,S,R)$ is a vertex partition such that
$L,R\neq\emptyset$ and there is no edge between $L$ and $R$. We say that a
terminal set $T$ is _$\phi$ -linked in $G$ _if, for any vertex cut $(L,S,R)$
in $G$, we have that $|S|\geq\phi\min\\{|(L\cup S)\cap T|,|(R\cup S)\cap
T|\\}$. If the whole set $V$ is _$\phi$ -linked_ in $G$, then we say $G$ is a
_$\phi$ -vertex-expander_. When $G$ is a $\frac{1}{n^{o(1)}}$-vertex-expander,
we usually just say that $G$ is a vertex expander. When $T$ is
$\frac{1}{n^{o(1)}}$-linked in $G$, then we say that $T$ is _well-linked_ $G$.

Our starting point is the observation that any vertex expander contains a low
degree spanning tree. More generally, if $T$ is well-linked in $G$, then there
is a low degree $T$-Steiner tree. Chekuri et al. [CKS05] showed how to compute
such tree in polynomial time. As this is too slow for us, we show that how to
compute it in almost-linear time:

######  Lemma 2.2.

There is a deterministic algorithm that, given any $\phi$-linked set $T$ in
$G$, compute a $T$-Steiner tree with maximum degree
$O(\frac{\log^{2}n}{\phi})$ in $\hat{O}(m)$ time.

###### Proof sketch.

We run in $\hat{O}(m)$ time the cut-matching game between vertices in $T$
where the cut player is from of [CGL+20] and the matching player is the
deterministic almost-linear time vertex max flow derived from [BGS22] (see
Lemma B.2 for the proof). Since $T$ is $\phi$-linked, the game must return an
embedding ${\cal P}$ of an expander $W$ where $V(W)=T$ and maximum degree
$O(\log n)$, where ${\cal P}$ has vertex congestion at most $O(\frac{\log
n}{\phi})$. The union of all paths in ${\cal P}$ will span $T$ can has maximum
degree $O(\frac{\log^{2}n}{\phi})$, which spans our desired $T$-Steiner tree.
∎

Of course, we cannot assume that $T$ itself is well-linked. However, via a
standard expander decomposition framework, the problem can be reduced to the
well-linked case modulo removing some vertices. To formally carry out this
approach, however, we will need a fast vertex expander decomposition
algorithm, and, indeed, we show how to achieve that in almost-linear-time (see
Theorem 4.3 and Corollary 4.4 for details):

######  Lemma 2.3 (Vertex Expander Decomposition with Terminals).

There is a deterministic algorithm that, given a graph $G=(V,E)$, a terminal
set $T\subseteq V$ and a parameter $\phi$, in $\hat{O}(m)$ time computes a
separator set $X$ of size $|X|\leq\phi|T|n^{o(1)}$ such that, for each
connected component $G_{i}=G[V_{i}]$ in $G\setminus X$, $T\cap V_{i}$ is
$\phi$-linked in $G_{i}$. In particular, if $T=V$, then $G_{i}$ is a
$\phi$-vertex expander.

##### Speed up the Low-degree Steiner Forest Decomposition.

Now, we are ready to speed up 2.1. Given a terminal set $T$, we call 2.3 with
$\phi=1/n^{o(1)}$ and obtain the vertex set $X$ of size at most $|T|/2$ such
that, for each connected component $G_{i}=G[V_{i}]$ in $G\setminus X$, we have
that $T\cap V_{i}$ is well-linked in $G_{i}$. Then, we just apply 2.2 on each
$G_{i}$ with terminal $T\cap V_{i}$. The union of Steiner tree on each $G_{i}$
gives us the $(T\setminus X)$-Steiner forest $F$ with maximum degree
$n^{o(1)}$ as desired.

To compute the low-degree hierarchy itself, we call the low-degree Steiner
forest decomposition $O(\log n)$ in the same way as in [DP20]. The idea is
simple. Set $T_{1}\leftarrow V$ as an initial terminal set. For any $i>1$, we
invoke 2.1 with terminal set $T\leftarrow T_{i-1}$ and obtain $T_{i}\leftarrow
X$. As $|T_{i}|\leq|T_{i-1}|/2$, we have $T_{O(\log n)}=\emptyset$. The low-
degree hierarchy is naturally defined based on $T_{1},T_{2},\dots$. See
Section 5.2 for details.

###  2.2 Optimal Deterministic Oracles

Next, we give an overview how to obtain a vertex-failure oracle with near-
optimal space and update time. (Achieving near optimal preprocessing and query
time is relatively simpler.) This part is discussed in Section 6 and Section 7
in details. We will start by describing the previous deterministic
construction with $\tilde{O}(md)$ space and $\tilde{O}(d^{3})$ update time of
[DP20]. Then, we show how to improve either space or update time individually.
Obtaining both improvement simultaneously turn out to be challenging. This is
the most technically involved step of this part and we will sketch the idea at
the end of the overview.

Throughout this overview, we will assume that the input graph $G=(L,R,E)$ is a
semi-bipartite graph (i.e. there is no edge between $R$). Moreover, $L$ is
spanned by a path $\tau$ and $\tau$ is given to us. This restricted structure
of $G$ will allows us to explain the key ideas more clearly. Actually, as
mentioned in Section 2.1, the low-degree hierarchy “almost” allows us to
reduce the problem to this case. So this assumption is almost without lost of
generality.

To simplify notations, assume further that $|L|=|R|=n$ and the vertex set $D$
to be deleted always contains $d$ vertices from $L$, denoted by $D_{L}$, and
$d$ vertices from $R$, denoted by $D_{R}$. In the updated graph $G\setminus
D$, the path $\tau$ will be split into $d+1$ connected intervals, denoted by
$\mathcal{I}=I_{1},\dots,I_{d+1}$. We call each interval $I\in\mathcal{I}$ a
_left interval_ (or simply an interval) and each vertex $v\in R$ a _right
vertex_. Sometimes, we use $\gamma$ to denote a right vertex, to make it
consistent with the main body of the paper. Let $A_{\gamma}\subseteq L$ denote
the ordered set of vertices adjacent to $\gamma$ with order consistent with
the path $\tau$.

To support connectivity queries in $O(d)$ time, given the set $D$, it suffices
(as shown in [DP10, DP20]) to compute connectivity between the left intervals
$\mathcal{I}$ in $G\setminus D$, i.e., whether $I$ and $I^{\prime}$ are in the
same connected components of $G\setminus D$ for every
$I,I^{\prime}\in\mathcal{I}$. Suppose the query is $(u,v)$. In the easy case
when both $u,v\in L$, we just identify the intervals $I$ containing $u$ and
$I^{\prime}$ containing $v$ in $O(1)$ time and answer if $I$ and $I^{\prime}$
are connected in $G\setminus D$ in $O(1)$. Now, even if $u\in R$, we can
identity a non-deleted neighbor $u^{\prime}$ of $u$ in $O(d)$ time as there
are only $O(d)$ deleted vertices. Note that $u^{\prime}\in L$ and, say,
$u^{\prime}\in I$. If $v\in R$, then we similarly find a neighbor
$v^{\prime}\in L$ of $v$ in $O(d)$ time, and say $v^{\prime}\in I^{\prime}$.
Finally, we answer if $I$ and $I^{\prime}$ are connected in $G\setminus D$.
The total query time is $O(d)$ time.

From now, we discuss how to preprocess $G$ using small space so that, given
$D$, we can compute the connectivity between the left intervals $\mathcal{I}$
in $G\setminus D$ fast. Below, for any set $L^{\prime},L^{\prime\prime}\subset
L$ on the left, we say that $L^{\prime}$ and $L^{\prime\prime}$ are _adjacent_
in $G$ if there exists an edge $(u,v)\in L\times L^{\prime\prime}$ or there
exists a right vertex $\gamma$ adjacent to both vertices in $L^{\prime}$ and
$L^{\prime\prime}$. We say that $L^{\prime}$ and $L^{\prime\prime}$ are
_adjacent via $(u,v)$_ in the former case and _adjacent via $\gamma$ _in the
latter case.

The bounds discussed below will be slightly better than our final bounds for
general graphs. More precisely, we will pay an additional $n^{o(1)}$ factor in
update time and $\omega(1)$-factor in space when apply the ideas together with
the low-degree hierarchy.

####  2.2.1 Warming-up: No right vertices.

To motivate the idea, consider the extremely simple case when $R=\emptyset$.
We will show a data structure with $O(m)$ space and $\tilde{O}(d^{2})$ update
time. In this case, the whole edge set $E(G)$ can be represented in a
2-dimentional table $\mathsf{Table}=[L]\times[L]$ where the entry $(u,v)$ is
the number of (multi-)edges between $u$ and $v$. Hence, during preprocessing
we can build a range counting data structure on this table, which takes
$O(|E(G)|)=O(m)$ space. Given the deletion set $D$ and so the left intervals
$\mathcal{I}$ are defined, we can check if $I$ and $I^{\prime}$ are adjacent
in $G\setminus D$ by querying the range counting data structure in
$\tilde{O}(1)$ time if

$|E(G)\cap(I\times I^{\prime})|>0.$

By querying between all pairs $I,I^{\prime}\in\mathcal{I}$, we deduce the
connected components of $\mathcal{I}$ in $\tilde{O}(d^{2})$ time.

####  2.2.2 Deterministic Construction of [DP20]: $\tilde{O}(md)$ space and
$\tilde{O}(d^{3})$ update time.

We first describe the deterministic construction of [DP20] that uses
$\tilde{O}(md)$ space and $\tilde{O}(d^{3})$ update time. We view the high-
level idea of [DP20] for handling right vertices as follows: Construct a
_restricted_ (multi-)graph $\hat{G}$ whose vertex set only contains
$V(\hat{G})=L$, but $\hat{G}$ should captures connectivity between left
vertices of $G$ _even after vertex deletions_. Since $\hat{G}$ contains only
left vertices, we can use the range counting idea on $\hat{G}$.

Here is a natural way to construct $\hat{G}$. Starting with $\hat{G}=G[L]$,
for each right vertex $\gamma\in R$, add a $(d+1)$-vertex connected graph on
its neighbors $A_{\gamma}\subseteq L$ (or a clique if $|A_{\gamma}|\leq d$),
in which the edges are called the artificial edges of $\gamma$, denoted by
$\hat{E}_{\gamma}$. Specially, we define $\hat{E}_{\gamma}=A_{\gamma}\times
B_{\gamma}$, where $B_{\gamma}\subseteq A_{\gamma}$ is an arbitrary subset of
size $\min\\{|A_{\gamma}|,d+1\\}$.888We note that the deterministic
construction in [DP20] did not define $\hat{E}_{\gamma}$ as a product set
$A_{\gamma}\times B_{\gamma}$, but their $\hat{E}_{\gamma}$ still forms a
$\min\\{|A_{\gamma},d+1|\\}$-connected graph on $A_{\gamma}$. Our product-set
construction will be crucial for faster update time as will be explained in
Section 2.2.3. Observe that $\hat{E}_{\gamma}$ spans $A_{\gamma}$ with the
following _fault-tolerant_ property: for any $D_{L}\subseteq L$,
$A_{\gamma}\setminus D_{L}$ (which are obliviously connected in $G\setminus
D_{L}$ via $\gamma$) are still connected in $\hat{G}\setminus D_{L}$. It
follows that, for any deleted set $D=D_{L}\cup D_{R}$, the graph
$\hat{G}_{D}:=\hat{G}\setminus(D_{L}\cup\bigcup_{\gamma\in
D_{R}}\hat{E}_{\gamma})$ preserves connectivity between all left vertices of
$G\setminus D$ and, in particular, between all left intervals $\mathcal{I}$.
So it suffices to computed components of $\mathcal{I}$ in $\hat{G}_{D}$. We
can query if $I$ and $I^{\prime}$ are adjacent in $\hat{G}_{D}$ by checking if

$|E(\hat{G})\cap(I\times I^{\prime})|-\sum_{\gamma\in
D_{R}}|\hat{E}_{\gamma}\cap(I\times I^{\prime})|>0,$

which can be computed using $1+|D_{R}|=O(d)$ range queries. By querying all
pairs, the connected components of $\mathcal{I}$ in $\hat{G}_{D}$ can be
deduced in $\tilde{O}(d^{3})$ time as desired. The total space for range
counting structures on $E(\hat{G})$ and all $\hat{E}_{\gamma}$ is
$\tilde{O}(|E(\hat{G})|+\sum_{\gamma}|\hat{E}_{\gamma}|)=\tilde{O}(|E(G)|+\sum_{\gamma}|A_{\gamma}|d)=\tilde{O}(md)$.

####  2.2.3 Update-Time Improvement: $\tilde{O}(md)$ space and
$\tilde{O}(d^{2})$ update time.

Then we will show how to deterministically improve the update time to
$\tilde{O}(d^{2})$. To improve the update time to $\tilde{O}(d^{2})$, the
high-level idea is that we want to avoid querying for all $O(d^{2})$ pairs of
left intervals $I,I^{\prime}\in\mathcal{I}$. We will use a
Bor$\mathring{\text{u}}$vka’s based algorithm instead, which can reduce the
number of queries to $\tilde{O}(d)$. However, the queries become more
complicated.

Recall that Bor$\mathring{\text{u}}$vka’s algorithm uses the “hook and merge”
approach. There are $O(\log|{\cal I}|)$ phases. In each phase there has
already been a partition of intervals ${\cal I}$ into groups $Z_{1},...,Z_{z}$
such that intervals in a same group are in a same connected component. In this
phase, these groups will be further merged by looking for an adjacent group
for each $Z_{k}$999Namely, find another group $Z_{k^{\prime}}$ such that some
$I^{\prime}\in Z_{k^{\prime}}$ and some $I\in Z_{k}$ are adjacent., which can
be reduced to some batched-adjacency queries: given $Z_{k}$ and a batch of
groups $Z_{l},Z_{l+1},...,Z_{r}$, is there any group in this batch adjacent to
$Z_{k}$? This query can be answered by checking if

$\sum_{I\in Z_{k}}\sum_{I^{\prime}\in Z_{l,r}}|E(\hat{G})\cap(I\times
I^{\prime})|-\sum_{\gamma\in D_{R}}\sum_{I\in Z_{k}}\sum_{I^{\prime}\in
Z_{l,r}}|\hat{E}_{\gamma}\cap(I\times I^{\prime})|>0,$ (1)

where $Z_{l,r}=\bigcup_{l\leq k^{\prime}\leq r}Z_{k^{\prime}}$. By further
exploiting the fact that each $\hat{E}_{\gamma}$ is a product set
$A_{\gamma}\times B_{\gamma}$, Inequality (1) is equivalent to

$\sum_{I\in Z_{k}}\sum_{I^{\prime}\in Z_{l,r}}|E(\hat{G})\cap(I\times
I^{\prime})|-\sum_{\gamma\in D_{R}}\left(\sum_{I\in Z_{k}}|A_{\gamma}\cap
I|\cdot\sum_{I^{\prime}\in Z_{l,r}}|B_{\gamma}\cap I^{\prime}|\right)>0.$

The key to fast update time is the following. We arrange intervals in an
ordered list ${\cal I}_{t}$ ($t$ denotes the phase number) such that ${\cal
I}_{t}$ is the concatenation of $Z_{1},...,Z_{z}$. Now, by preprocessing a
2D-counting table $\mathsf{Table}_{t}=\\{|E(\hat{G})\cap(I\times
I^{\prime})|\\}_{I\times I^{\prime}\in{\cal I}_{t}\times{\cal I}_{t}}$ with
size $|{\cal I}|^{2}$, the first term can be answered by a single 2D-range
counting query on $\mathsf{Table}_{t}$. Next, by preprocessing, for each
$\gamma\in D_{R}$, a 1D counting array
$\textsf{A-Array}_{\gamma,t}=\\{|A_{\gamma}\cap I|\\}_{I\in{\cal I}_{t}}$ and
another 1D array $\textsf{B-Array}_{\gamma,t}=\\{|B_{\gamma}\cap
I|\\}_{I\in{\cal I}_{t}}$, the second term can be answered using $2|D_{R}|$
queries to these arrays $\textsf{A-Array}_{\gamma,t}$ and
$\textsf{B-Array}_{\gamma,t}$. Therefore, the query time for each batched-
adjacency query is $\tilde{O}(d)$. For each phase, we make $\tilde{O}(d)$ such
queries which take $\tilde{O}(d^{2})$ total query time. Notice that since the
ordered list ${\cal I}_{t}$ will be shuffled between phases,
$\mathsf{Table}_{t},\textsf{A-Array}_{\gamma,t}$ and
$\textsf{B-Array}_{\gamma,t}$ must be rebuilt at the beginning of each phase.
But this takes $\tilde{O}(d^{2})$ total time. Over all $O(\log|\cal{I}|)$
phases, the total update time is $\tilde{O}(d^{2})$.

We emphasize that this approach highly relies on that each $\hat{E}_{\gamma}$
is a product set $A_{\gamma}\times B_{\gamma}$, which enables us to consider
two dimensions separately. If $\hat{E}_{\gamma}$ is less structured, a 2D
counting table is required for each $\gamma\in D_{R}$ in this approach, and we
cannot afford to construct them in $\tilde{O}(d^{2})$ update time. The space
is still $O(md)$ as shown above. Note that this is an inherent limitation of
this approach. As long as $\hat{E}_{\gamma}$ forms
$\min\\{|A_{\gamma}|,d+1\\}$-connected graph on $A_{\gamma}$, we will have
space $\Omega(md)$ in the worst case.

####  2.2.4 Space Improvement: $O(m)$ space and $\tilde{O}(d^{3})$ update
time.

Now, we will improve the space to $O(m)$, but it will bring the update time
back to $\tilde{O}(d^{3})$. This step already gives the first deterministic
oracle with near-linear space. The high-level idea is to relax the fault-
tolerant property in order to get sparser artificial edges. Concretely, it is
acceptable that, for some right vertices $\gamma$, its artificial edges
$\hat{E}_{\gamma}$ do not satisfy the fault-tolerant property, but we want the
number of such vertices to be small so we can afford to “repair” their
$\hat{E}_{\gamma}$ in an additional repairing phase of the update algorithm.
We note that the Monte Carlo construction in [DP20] also takes advantage of a
similar relaxation.

Towards this goal, let $\hat{E}=\bigcup_{\gamma\in R}\hat{E}_{\gamma}$
contains all artificial edges. We will redefine the artificial edges
$\hat{E}_{\gamma}$ of $\gamma$ so that the total number of artificial edges
not counting multiplicity, denoted by $\|\hat{E}\|_{0}$, is linear to
$\sum_{\gamma\in R}|A_{\gamma}|=O(m)$. The construction works by scanning
through right vertices $\gamma\in R$ one by one. Initialize
$\hat{E}=\emptyset$. Then, for each $\gamma$, if $(u,v)\in\hat{E}$ for all
$(u,v)\in A_{\gamma}\times B_{\gamma}$ (as before $B_{\gamma}\subseteq
A_{\gamma}$ is an arbitrary subset with size $\min\\{|A_{\gamma}|,d+1\\}$),
then define $\hat{E}_{\gamma}=A_{\gamma}\times B_{\gamma}$. Otherwise, if
there exists $(u_{\gamma},v_{\gamma})\notin\hat{E}$ where
$u_{\gamma},v_{\gamma}\in A_{\gamma}$, then set
$\hat{E}_{\gamma}=A_{\gamma}\times\\{u_{\gamma},v_{\gamma}\\}$. Lastly, we
insert $\hat{E}_{\gamma}$ into $\hat{E}$ and proceed to the next right vertex.
Note that although $\sum_{\gamma\in R}|\hat{E}_{\gamma}|$ can be large,
$\|\hat{E}\|_{0}$ is bounded by the number of new artificial edges added in
each round. Since there is no new edge in the former case, it follows that
$\|\hat{E}\|_{0}=\sum_{\gamma\in R}|A_{\gamma}|=O(m)$.

We then show there are only a few $\hat{E}_{\gamma}$ without the fault-
tolerant property. Let $R_{\mathrm{fault}}$ contain all $\gamma$ where $D_{L}$
contains both $u_{\gamma}$ and $v_{\gamma}$. Observe that $A_{\gamma}\setminus
D_{L}$ is not connected by $\hat{E}_{\gamma}\setminus D_{L}$ only if
$\gamma\in R_{\mathrm{fault}}$. As $D_{L}$ contains at most $|D_{L}|^{2}$
different pairs of vertices, so
$|R_{\mathrm{fault}}|\leq|D_{L}|^{2}=O(d^{2})$. Therefore, we have that the
graph $\hat{G}_{D}:=\hat{G}\setminus(D_{L}\cup\bigcup_{\gamma\in
D_{R}}\hat{E}_{\gamma})$ still preserves preserves connectivity between all
left intervals of $G\setminus D$, except that it might miss the connectivity
information from each $\gamma\in R_{\mathrm{fault}}$.

To compute the connected components of $\mathcal{I}$ in $G\setminus D$, we
fist compute connected components of $\mathcal{I}$ in $\hat{G}_{D}$. This can
be done in $\tilde{O}(d^{2})$ time as in Section 2.2.3. But then some
connected components $\mathcal{I}$ in $\hat{G}_{D}$ may be further connected
via $\gamma\in R_{\mathrm{fault}}$. Therefore, we add a _reparing phase_ in
the update algorithm. For every $I\in\mathcal{I}$ and $\gamma\in
R_{\mathrm{fault}}$, we simply check $I\cap A_{\gamma}\neq\emptyset$. If there
is some $I,I^{\prime}\in{\cal I}$ and $\gamma\in R_{\mathrm{fault}}$ such that
$I\cap A_{\gamma}\neq\emptyset$ and $I^{\prime}\cap A_{\gamma}\neq\emptyset$,
then the connected components of $I$ and $I^{\prime}$ can be merged as $I$ and
$I^{\prime}$ are adjacent via $\gamma$. After these queries, we can finally
deduce connected components of $\mathcal{I}$ in $G\setminus D$. We can check
if $I\cap A_{\gamma}\neq\emptyset$ in $\tilde{O}(1)$ time. However, there are
$O(d^{3})$ pairs of $I,I^{\prime}\in\mathcal{I}$ and $\gamma\in
R_{\mathrm{fault}}$, the repairing phase needs $\tilde{O}(d^{3})$ time.

Therefore, we obtain an oracle with $O(m)$ space and $\tilde{O}(d^{3})$ update
time.

####  2.2.5 Repairing-Time Improvement: $\tilde{O}(d^{3})$ update time with
$\tilde{O}(d^{2})$ repairing time

As a prerequisite to our final construction in Section 2.2.6, here we will
improve the running time of the repairing phase from $\tilde{O}(d^{3})$ to
$\tilde{O}(d^{2})$. However, the total update time would still be
$\tilde{O}(d^{3})$. because our artificial edges $\hat{E}_{\gamma}$ in this
step will not be well-structured and so we cannot apply the
Bor$\mathring{\text{u}}$vka’s based algorithm for interval connectivity as we
did in Section 2.2.3. We will sketch how to handle this issue in Section
2.2.6.

The high-level idea is to redesign the artificial edges $\hat{E}_{\gamma}$ for
each $\gamma\in R$, such that for any failure set $D$, vertices in
$A_{\gamma}\setminus D_{L}$ may not be connected by $\hat{E}_{\gamma}\setminus
D_{L}$ itself, but they will be connected by
$(\hat{E}_{\gamma}\cup\hat{F}_{\gamma})\setminus D_{L}$, where
$\hat{F}_{\gamma}$ is a small set of $D$-repairing edges generated after $D$
is deleted. In fact, in our following construction, the total number of
$D$-repairing edges for all $\gamma$ is bounded by $O(d^{2})$. Therefore, the
repairing phase only needs to add the connectivity provided by these repairing
edges and it takes $\tilde{O}(d^{2})$ time.

We introduce a new structure called the segmentation hierarchy. For each
$\gamma\in R$, the segmentation hierarchy ${\cal S}_{\gamma}$ is simply a
recursive division of $A_{\gamma}$ like a segment tree. The elements of ${\cal
S}_{\gamma}$ are segments, which are consecutive sublists of $A_{\gamma}$.
${\cal S}_{\gamma}$ is partitioned into $r=O(\log|A_{\gamma}|)$ levels ${\cal
S}_{\gamma,1},...,{\cal S}_{\gamma,r}$ such that for each level $j$, segments
in ${\cal S}_{\gamma,j}$ partition the list $A_{\gamma}$. In particular, the
top level has the unique segment $A_{\gamma}$ and each segment at the bottom
level is a singleton list of each vertex in $A_{\gamma}$. Furthermore, for
each level $j\geq 2$, each segment $S\in{\cal S}_{\gamma,j}$ is the union of
two child-segments $S_{1},S_{2}\in{\cal S}_{\gamma,j-1}$. See Definition 6.9
for the complete definition.

The construction of $\hat{E}_{\gamma}$ is similar to the previous step. We
process $\gamma\in R$ one by one and initialize $\hat{E}=\emptyset$. Let
$B_{\gamma}$ be an arbitrary subset of $A_{\gamma}$ of size
$\min\\{d+1,|A_{\gamma}|\\}$. For each $\gamma\in R$ if there are less than
$|{\cal S}_{\gamma}|$ pairs in $(A_{\gamma}\times
B_{\gamma})\setminus\hat{E}$, we set $\hat{E}_{\gamma}=A_{\gamma}\times
B_{\gamma}$ as usual. Otherwise we assign a distinct pair
$(u_{S},v_{S})\in(A_{\gamma}\times B_{\gamma})\setminus\hat{E}$ to each
segment $S\in{\cal S}_{\gamma}$ and let $\hat{E}_{\gamma}=\sum_{S\in{\cal
S}_{\gamma}}S\times\\{u_{S},v_{S}\\}$. Lastly, insert $\hat{E}_{\gamma}$ to
$\hat{E}$ and proceed to the next $\gamma$. Now, we claim that the total
number of artificial edges (without multiplicity) is
$\|\hat{E}\|_{0}=\tilde{O}(m)$ since the former case will bring at most
$|{\cal S}_{\gamma}|$ new edges and in the latter case the number of new edges
is at most $|\hat{E}_{\gamma}|=O(\sum_{S\in{\cal
S}_{\gamma}}|S|)=\tilde{O}(|A_{\gamma}|)$. So $\|\hat{E}\|_{0}=\sum_{\gamma\in
R}\tilde{O}(|A_{\gamma}|)=\tilde{O}(m)$ and so the total space is
$O(\|\hat{E}\|_{0})=\tilde{O}(m)$.

The repairing algorithm is based on the segmentation hierarchy. Let ${\cal
S}_{\mathrm{fault}}$ contain all segments $S$ (in ${\cal S}_{\gamma}$ for all
$\gamma\in R$) such that $u_{S},v_{S}\in D_{L}$. By the same argument,
$S\setminus D_{L}$ is not connected by $\hat{E}_{\gamma}\setminus D_{L}$ only
if $S\in{\cal S}_{\mathrm{fault}}$, and we have $|{\cal
S}_{\mathrm{fault}}|=O(d^{2})$. For each $\gamma\in R$ with nonempty ${\cal
S}_{\mathrm{fault}}\cap{\cal S}_{\gamma}$, suppose that we are given a non-
deleted vertex $v_{\gamma}\in A_{\gamma}\setminus D_{L}$.101010In the complete
algorithm, the $v_{\gamma}$ for each $\gamma\in R$ with ${\cal
S}_{\mathrm{fault}}\cap{\cal S}_{\gamma}\neq\emptyset$ can be computed in
totally $\tilde{O}(d^{2})$ time. Then we construct $D$-repairing edges
$\hat{F}_{\gamma}$ by, for each $S\in{\cal S}_{\mathrm{fault}}\cap{\cal
S}_{\gamma}$, connecting its two child-segments $S_{1},S_{2}$ to $v_{\gamma}$.
Concretely, we add to $\hat{F}_{\gamma}$ four $D$-repairing edges connecting
$v_{\gamma}$ to each of $u_{S_{1}},v_{S_{1}},u_{S_{2}},v_{S_{2}}$ for each
$S\in{\cal S}_{\mathrm{fault}}\cap{\cal S}_{\gamma}$. Thus there are totally
$O(|{\cal S}_{\mathrm{fault}}|)=O(d^{2})$ $D$-repairing edges and the
repairing time is $\tilde{O}(d^{2})$.

To see the correctness, we say that a segment $S$ is _maximal_ if
$S\in\mathcal{S}_{\gamma}\setminus\mathcal{S}_{\mathrm{fault}}$ but its
parent-segment is in $\mathcal{S}_{\gamma}\cap\mathcal{S}_{\mathrm{fault}}$.
Observe that maximal segments cover $A_{\gamma}\setminus D$, the whole non-
deleted part of $A_{\gamma}$. Now, for each maximal segment $S$, we have that
either $u_{S}\notin D$ or $v_{S}\notin D$. Say $u_{S}\notin D$, so $u_{S}$ is
connected to $v_{\gamma}$ via $\hat{F}_{\gamma}$ and the whole $S$ is
connected to $u_{S}$ via $\hat{E}_{\gamma}$. Therefore, indeed we have that
vertices in $A_{\gamma}\setminus D$ will be connected via
$(\hat{E}_{\gamma}\cap\hat{F}_{\gamma})\setminus D$ as promised.

####  2.2.6 Final Algorithm: $\tilde{O}(m)$ space and $\tilde{O}(d^{2})$
update time.

The last step to our final algorithm is to make $\hat{E}_{\gamma}$ in Section
2.2.5 well-structured. We cannot hope each $\hat{E}_{\gamma}$ forms a perfect
product set because of the segmentation hierarchy. Yet, we can still design it
to have some good structural property so that it is compatible with the
Bor$\mathring{\text{u}}$vka’s based algorithm in Section 2.2.3, which finally
leads us to $\tilde{O}(d^{2})$ update time and $\tilde{O}(m)$ space
simultaneously.

The construction algorithm of artificial edges is relatively simple. We only
summarize the outputs here and see Section 6.4 for details. For each right
vertex $\gamma\in R$, we still assign a pair $(u_{S},v_{S})\in
A_{\gamma}\times A_{\gamma}$ to each segment $S\in{\cal S}_{\gamma}$, and the
actual $\hat{E}_{\gamma}$ will be

$\hat{E}_{\gamma}=A_{\gamma}\times B_{\gamma}+\sum_{S\in{\cal
S}_{\gamma}}S\times\\{u_{S}\\},$

where $B_{\gamma}$ is designed so that there will be
$\|\hat{E}\|_{0}=\tilde{O}(m)$ distinct artificial edges using similar
argument as in Section 2.2.5. So the space bound is $\tilde{O}(m)$

Now, we discuss how this structure enables $\tilde{O}(d^{2})$ update time. For
each $S\in{\cal S}_{\gamma}$, we call $u_{S}$ the witness of $S$. Furthermore,
let $f:{\cal S}_{\gamma}\to A_{\gamma}$ be the witness function defined by
$f(S)=u_{S}$ for each $S\in{\cal S}_{\gamma}$. Our construction ensures that
$f$ has the following monotonically increasing property on each level ${\cal
S}_{\gamma,j}$: for each $S,S^{\prime}\in{\cal S}_{\gamma,j}$ such that $S$ is
located before $S^{\prime}$ on $A_{\gamma}$, $f(S)$ is located before
$f(S^{\prime})$ according the order of vertices in $A_{\gamma}$.

Answering a batched-adjacency query in Section 2.2.3 given $Z_{k}$ and
$Z_{l,r}$ now becomes more involved. We sketch the ideas below and see Section
7.2 for details. The product term $A_{\gamma}\times B_{\gamma}$ is easy to
deal with using the idea in Section 2.2.3. To handle the term $\sum_{S\in{\cal
S}_{\gamma}}S\times f(S)$, we first write down its contribution to the second
term of Inequality (1) for fixed $\gamma\in D_{R}$, level $j$ and $I\in Z_{k}$
as

$Q(\gamma,j,I)=\left|\left(\sum_{S\in{\cal S}_{\gamma,j}}S\times
f(S)\right)\cap\left(\bigcup_{I^{\prime}\in Z_{l,r}}I^{\prime}\times
I\right)\right|.$

In fact, there will be totally at most $\tilde{O}(d^{2})$ queries on
$Q(\gamma,j,I)$, summing over different $\gamma,j,I$ in all
Bor$\mathring{\text{u}}$vka’s phases. In what follows, we discuss how to
compute $Q(\gamma,j,I)$ for fixed $\gamma,j,I$ in $\tilde{O}(1)$ time.

Recall that $I$ is an interval on the path $\tau$. Consider the set of
segments $\\{S\in\mathcal{S}_{\gamma,j}\mid f(S)\in I\\}$, i.e., the set of
level-$j$ segments whose witnesses are in $I$. By the monotonically increasing
property of $f$, observe that the union of these segments form a consecutive
sublist of $A_{\gamma}$, denoted by $A_{\gamma}(v_{L},v_{R})$. Then the
contribution can be rewritten as

$Q(\gamma,j,I)=\left|A_{\gamma}(v_{L},v_{R})\cap\bigcup_{I^{\prime}\in
Z_{l,r}}I^{\prime}\right|.$

This query can be further reduced to one 3D range counting query by exploiting
that intervals $I^{\prime}$ in $Z_{l,r}$ locate consecutively in the order
${\cal I}_{t}$ for the $t$-th Bor$\mathring{\text{u}}$vka’s phase. Therefore,
$Q(\gamma,j,I)$ can be indeed queried in $\tilde{O}(1)$ time. Moreover, the
required data structures can be constructed in $\tilde{O}(d^{2})$ time at the
beginning of each Bor$\mathring{\text{u}}$vka’s phase.

##### Perspective: Repairable Hypergraph-to-Graph Connectivity-Sparsifiers.

Lastly we discuss our techniques in Section 2.2 in a different perspective. If
we corresponds left vertices and right vertices in the semi-bipartite graph to
vertices and hyperedges in a hypergraph respectively, the techniques on
constructing artificial edges and $D$-repairing edges can be viewed as some
kind of sparsifier which transform a hypergraph $H$ to a graph $G$.
Concretely, the transformation will keep the vertex set unchanged, and for
each hyperedge $e\in E(H)$, add an edge set $\hat{E}(e)$ to $E(G)$. Namely we
will have $V(G)=V(H)$ and $E(G)=\bigcup_{e\in E(H)}\hat{E}(e)$. Moreover, the
sparsifier has the following properties.

  * •

(Vertex Restricted) The vertex set is unchanged.

  * •

(Sparse) The number of edges in $G$ is nearly linear to the total size of
edges in $H$. Namely $|E(G)|=\tilde{O}(\sum_{e\in E(H)}|e|)$, where we use the
same notation $e$ to denote the set of $e$’s endpoints.

  * •

(Fault-Tolerant/Repairable) Given any failure set $D\subseteq V(G)$ with
$|D|=d$, by augmenting each $\hat{E}(e)$ with a set $\hat{F}(e)$ of repairing
edges, it will be guaranteed that for each hyperedge $e\in E(H)$, vertices in
$e$ are still connected by $\hat{E}(e)\cup\hat{F}(e)$. Moreover, the total
size of $\hat{F}(e)$ summing over all $e\in E(H)$ is $\tilde{O}(d^{2})$, and
all nonempty $\hat{F}(e)$ can be computed in totally $\tilde{O}(d^{2})$ time.

We apply this tool to obtain an nearly optimal vertex-failure connectivity
oracle. Furthermore, we note that this sparsifier is somewhat stronger than
maintaining just pairwise connectivity because the connectivity of each
hyperedge $e$ is perserved by $\hat{E}(e)\cup\hat{F}(e)$ individually. Thus we
expect that this tool or its variant can have applications on other vertex-
failure problems.

##  3 Preliminaries

Throughout the paper, we use the standard graph theoretic notation. For any
graph, we use $V(\cdot)$ and $E(\cdot)$ to denote its vertex set and edge set
respectively. If there is no other specification, $G$ will denote the graph on
which we build the oracle and we set $n=|V(G)|$ and $m=|E(G)|$. Given a graph
$G=(V(G),E(G))$, for any $S\subseteq V(G)$, we let $G[S]$ denote the subgraph
of $G$ induced by vertices $S$, and let $N_{G}(S)=\\{u\mid(u,v)\in
E(G),u\notin S,v\in S\\}$ denote the set of vertices adjacent to $S$. Also,
for any $S\subseteq V(G)$, we use $G\setminus S$ to denote the graph after
removing vertices in $S$ and edges incident to them. Similarly, for any
$F\subseteq E(G)$, $G\setminus F$ denote the graph after removing edges in
$F$.

In this paper, we will use ordered lists frequently. An ordered list $L$ is a
list of totally ordered elements, and it inherits properties and operations
from sets. We say for each $1\leq k\leq|L|$ the $k$-th element (denoted by
$L(k)$) has rank $k$ on $L$ or has $L$-rank $k$, and let $L(k_{1},k_{2})$
denote the consecutive sublist from rank $k_{1}$ to $k_{2}$. We define an
operations on ordered list called restrictions as follows. Assume we have an
ordered list $L$ as the base. Let $L^{\prime}$ be a sublist (maybe
inconsecutive) of $L$ and let $\bar{L}$ be a consecutive sublist on $L$. The
restriction of $\bar{L}$ on $L^{\prime}$, denoted by $\bar{L}\cap L^{\prime}$,
is a consecutive sublist on $L^{\prime}$ that contains elements in
$\bar{L}\cap L^{\prime}$. When $L^{\prime}$ is stored explicitly (with the
$L$-rank of each element), the restriction $\bar{L}\cap L^{\prime}$ will be
stored as two integers in our algorithm, namely the $L^{\prime}$-ranks of the
leftmost and rightmost element of $\bar{L}\cap L^{\prime}$, and they can be
computed in $O(\log|L^{\prime}|)$ time via the binary search.

We also use the notion of multisets. A multiset $M$ is a set but allows
repeated elements. We let $|M|$ denote its size counting multiplicity, while
we let $\|M\|_{0}$ denote its size without multiplicity. For two multisets
$M_{1}$ and $M_{2}$, we call their multiset-union as their sum, denoted by
$M_{1}+M_{2}$, and we use $\sum_{i=1}^{k}M_{i}$ denote the multiset-union of
several multisets $M_{1},...,M_{k}$. The intersection of a multiset $M$ and a
set $S$ is still a multiset denoted by $M\cap S$. Concretely, for each element
of $M$, it will be kept in $M\cap S$ if it is in $S$, otherwise it will be
dropped.

##  4 Weighted Vertex Expander Decomposition

In this section, we introduce an almost-linear time algorithm to compute a
vertex expander decomposition of an undirected graph $G$ with non-negative
weight function $w(v)$ and demand function $\boldsymbol{\mathrm{d}}(v)$ on its
vertices $v\in V(G)$. For simplicity, we denote the total weight for a set
$S\subseteq V(G)$ by $w(S)=\sum_{v\in S}w(v)$, and similarly the total demand
for $S$ is $\boldsymbol{\mathrm{d}}(S)=\sum_{v\in
S}\boldsymbol{\mathrm{d}}(v)$131313We use such notations for other weight
functions throughout the paper.. The term vertex expander refers to some
“highly connected” graph in the sense that there is no sparse vertex cut, or
strictly speaking, it has high vertex expansion (see Definition 4.1).

######  Definition 4.1 (Weighted Vertex Expansion).

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be a graph with weight $w(v)\geq
0$ and demand $\boldsymbol{\mathrm{d}}(v)\geq 0$ for vertex each $v\in V(G)$.
A vertex cut of $G$ is a partition $(L,S,R)$ of $V(G)$ such that $(u,v)\notin
E(G)$ for all $u\in L,v\in R$. For any vertex cut $(L,S,R)$ of $G$, if
$\boldsymbol{\mathrm{d}}(L\cup S)>0$ and $\boldsymbol{\mathrm{d}}(R\cup S)>0$,
it has vertex expansion

$h_{G}(L,S,R)=\frac{w(S)}{\min\\{\boldsymbol{\mathrm{d}}(L\cup
S),\boldsymbol{\mathrm{d}}(R\cup S)\\}}.$

The vertex expansion of $G$, denoted by $h(G)$, is the minimum vertex
expansion of any vertex cut $(L,S,R)$ of $G$ with
$\boldsymbol{\mathrm{d}}(L\cup S),\boldsymbol{\mathrm{d}}(R\cup S)>0$.

In a vertex expander decomposition of $G$, $G$ will be separated by a small
fraction vertices called the separator, such that after removing the
separator, each of the remaining connected components is a vertex expander.
See Definition 4.2 for details.

######  Definition 4.2 (Weighted Vertex Expander Decomposition).

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be a graph with weight $w(v)\geq
0$ and demand $\boldsymbol{\mathrm{d}}(v)\geq 0$ for each vertex $v\in V(G)$.
For parameters $\epsilon>\phi>0$, an $(\epsilon,\phi)$-vertex expander
decomposition of $G$ is a collection ${\cal G}=(V_{1},...,V_{k})$ of disjoint
subsets of $V(G)$. Let $X=V(G)\setminus(\bigcup_{i}V_{i}$) denote the
separator. Then ${\cal G}$ further satisfies the following.

  * •

for each pair of distinct $V_{i},V_{i^{\prime}}\in{\cal G}$, there is no edge
connecting $V_{i}$ and $V_{i^{\prime}}$,

  * •

for all $V_{i}\in{\cal G}$, $h(G[V_{i}])\geq\phi$, and

  * •

$w(X)\leq\epsilon\cdot\boldsymbol{\mathrm{d}}(V(G))$.

This section is dedicated to show the fast deterministic vertex expander
decomposition algorithm as stated in Theorem 4.3. We note that there has been
a long line of works on fast expander decomposition e.g. [ST04, NS17, SW19,
CGL+20]. The first deterministic almost-linear time algorithm for expander
decomposition in the edge cut setting has been shown in [CGL+20] and later it
was generalized to weighted graphs in [LS21]. We follow the approach in
[CGL+20] and generalize it to the vertex expander and weighted setting.
Although the required techniques and tools have been developed, we remark that
to the best of our knowledge, an efficient algorithm on vertex expander
decomposition has never been shown explicitly in the literature before.

######  Theorem 4.3.

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be an $n$-vertex $m$-edge graph
with for each $v\in V(G)$, integral weight $1\leq w(v)\leq U$ and integral
demand $0\leq\boldsymbol{\mathrm{d}}(v)\leq w(v)$. Given parameters
$0<\epsilon\leq 1$, $1\leq
r\leq\lfloor\log_{20}\boldsymbol{\mathrm{d}}(V(G))\rfloor$, there is an
algorithm that computes an $(\epsilon,\phi)$-vertex expander decomposition of
$G$, where $\phi=\epsilon/(\log^{O(r)}U\log^{O(r^{5})}(m\log U))$. The
algorithm can be deterministic with running time $O(m^{1+o(1)+O(1/r)}\cdot
U^{1+O(1/r)}\cdot\log^{O(r^{4})}(mU)/\phi)$, or randomized with running time
$O(m^{1+o(1)}\cdot(mU)^{O(1/r)}\cdot\log^{O(r^{4})}(mU))$ and high correct
probability.

######  Corollary 4.4.

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be an $n$-vertex $m$-edge graph
with non-negative real weight $w(v)\geq 0$ and demand
$\boldsymbol{\mathrm{d}}(v)\geq 0$ for each vertex $v\in V(G)$. Let $U$ be the
ratio bound of both weight and demand such that $\frac{\max
w(v)}{\min_{w(v)>0}w(v)},\frac{\max\boldsymbol{\mathrm{d}}(v)}{\min_{\boldsymbol{\mathrm{d}}(v)>0}\boldsymbol{\mathrm{d}}(v)}\leq
U$. Given parameter $\epsilon>0$, there is an algorithm that computes an
$(\epsilon,\phi)$-vertex expander decomposition of $G$, where
$\phi=\epsilon/(m^{o(1)}U^{o(1)})$. The algorithm can be deterministic with
running time $O(m^{1+o(1)}\cdot U^{1+o(1)}/\phi)$, or randomized with running
time $O(m^{1+o(1)}\cdot U^{o(1)})$ and high correct probability.

######  Remark 4.5.

In the following of Section 4, we only discuss the less efficient
deterministic algorithm in Theorem 4.3. It suffices for our application in
Section 5 because we have $\phi=1/n^{o(1)}$ and $U=O(1)$ in that scenario. We
emphasize that we can improve the running time at a cost of making the
algorithm randomized, by simply substituting the approximate vertex-capacitaed
max flow algorithm in Lemma B.2 with the faster randomized version in Lemma
B.1.

Theorem 4.3 follows the natural divide-and-conquer paradigm which invokes an
efficient algorithm in Lemma 4.6 as a subroutine. Roughly speaking, the
subroutine will either return a balanced sparse vertex cut (a vertex cut is
balanced if it has large demands on both sides), or exhibit a large vertex
expander separated from the other part by a sparse vertex cut. In both cases,
the graph size of the recursive calls will shrink by a constant factor.
Corollary 4.4 is a corollary of Theorem 4.3 where the condition on weights and
demands is relaxed and the formula of time complexity is simplified. The
complete proof of Theorem 4.3 and Corollary 4.4 is shown in Section A.1.

######  Lemma 4.6.

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be an $n$-vertex $m$-edge graph
with, for each $v\in V(G)$, integral weight $1\leq w(v)\leq U$ and integral
demand $0\leq\boldsymbol{\mathrm{d}}(v)\leq w(v)$. Given parameters
$0<\epsilon\leq 1$ and $1\leq
r\leq\lfloor\log_{20}\boldsymbol{\mathrm{d}}(V(G))\rfloor$, there is a
deterministic algorithm that computes a vertex cut $(L,S,R)$ (possibly
$L=S=\emptyset$) of $G$ with
$w(S)\leq\epsilon\cdot\boldsymbol{\mathrm{d}}(L\cup S)$ which further
satisfies

  * •

either $\boldsymbol{\mathrm{d}}(L\cup S),\boldsymbol{\mathrm{d}}(R\cup
S)\geq\boldsymbol{\mathrm{d}}(V(G))/3$; or

  * •

$\boldsymbol{\mathrm{d}}(R)\geq\boldsymbol{\mathrm{d}}(V(G))/2$ and
$h(G[R])\geq\phi$ for some $\phi=\epsilon/(\log^{O(r)}U\log^{O(r^{5})}(m\log
U))$.

The running time of this algorithm is $O(m^{1+o(1)+O(1/r)}\cdot
U^{1+O(1/r)}\cdot\log^{O(r^{4})}(mU)/\phi)$.

Lemma 4.6 is an application of the cut-matching-game framework. We first
introduce the cut-matching game in Section 4.1. Then in Section 4.2, we
exploit the cut-matching-game framework to solve the most-balanced vertex cut
problem (see Lemma 4.14), which is a critical step getting to Lemma 4.6. The
complete proof of Lemma 4.6 using Lemma 4.14 is in Section A.4.

###  4.1 The Cut-Matching Game

The cut-matching game is an interactive process between a cut player and a
matching player to construct an expander. The goal of the cut player is to
ensure the game will terminate with an expander in a small number of rounds,
while the matching player can act arbitrarily or even adversarially to slow
down this process. The game was first introduced by Khandekar, Rao and
Variranzi [KRV09] to design fast algorithm to compute sparse cuts and balanced
cuts.

Before we describe the cut-matching game, we emphasize that the game is
designed under the edge cut setting, where whether an edge cut is sparse or
not is measured by its sparsity as defined in Definition 4.7, and a graph is
an expander if there is no sparse edge cut.

######  Definition 4.7 (Sparsity).

Let $H=(V(H),E(H),w_{H},\boldsymbol{\mathrm{d}})$ be a graph with weight
$w(e)\geq 0$ for each edge $e\in E(H)$ and demand
$\boldsymbol{\mathrm{d}}(v)\geq 0$ for each vertex $v\in V(H)$. For any edge
cut $(S,V(H)\setminus S)$ with
$0<\boldsymbol{\mathrm{d}}(S)<\boldsymbol{\mathrm{d}}(V(H))$, it has sparsity

$\Psi_{H}(S,V(H)\setminus S)=\frac{w_{H}(E_{H}(S,V(H)\setminus
S))}{\min\\{\boldsymbol{\mathrm{d}}(S),\boldsymbol{\mathrm{d}}(V(H)\setminus
S)\\}},$

where $E_{H}(S,V(H)\setminus S)$ is the set of edges crossing the cut
$(S,V(H)\setminus S)$ and $w_{H}(E^{\prime})=\sum_{e\in E^{\prime}}w(e)$ for
any $E^{\prime}\subseteq E(H)$. The sparsity of $H$, denoted by $\Psi(H)$, is
the minimum sparsity of any edge cut $(S,V(H)\setminus S)$ with
$0<\boldsymbol{\mathrm{d}}(S)<\boldsymbol{\mathrm{d}}(V(H))$.

The game we exploited is actually a variant by Khandekar et al. [KKOV07], and
we will use it in a weighted setting. Specifically, the cut-matching game
starts with a graph $H=(V(H),E(H),w_{H},\boldsymbol{\mathrm{d}})$, where each
vertex $v\in V(G)$ has integral demands $0\leq\boldsymbol{\mathrm{d}}(v)\leq
U$ and the edge set $E(H)$ is empty. During the game, $E(H)$ will grow and
each edge $e\in E(H)$ will have integral weight $1\leq w_{H}(e)\leq U$. When
the game ends, $H$ will be guaranteed to be an expander with proper sparsity.

The cut-matching game has several rounds. In the $i$-th round, the cut player
will choose a cut $(A_{i},B_{i})$ of $V(H)$ with
$\boldsymbol{\mathrm{d}}(B_{i})\geq\boldsymbol{\mathrm{d}}(A_{i})\geq\boldsymbol{\mathrm{d}}(V(H))/4$
and $w_{H}(E_{H}(A_{i},B_{i}))\leq\boldsymbol{\mathrm{d}}(V(H))/100$. If no
such cut exists, it can be proved that there must be a set $S\subseteq V(H)$
such that $\boldsymbol{\mathrm{d}}(S)\geq\boldsymbol{\mathrm{d}}(V(H))/2$ and
$H[S]$ can be certificated as an expander. The cut player will choose the cut
$(A_{i},B_{i})=(V(H)\setminus S,S)$, and the game will terminate right after
this round. Given the current graph $H$ and the cut $(A_{i},B_{i})$ chosen by
the cut player, the matching player should choose an arbitrary
$\boldsymbol{\mathrm{d}}$-matching $M_{i}$ with value
$M_{i}(A_{i})=\boldsymbol{\mathrm{d}}(A_{i})$ (see Definition 4.8) between
$A_{i}$ and $B_{i}$, and then this matching $M_{i}$ will be added to $E(H)$.

######  Definition 4.8 ($\boldsymbol{\mathrm{d}}$-matching).

For two sets $A,B$ of vertices with demand $\boldsymbol{\mathrm{d}}(v)\geq 0$
for each $v\in A\cup B$ (assuming
$\boldsymbol{\mathrm{d}}(A)\leq\boldsymbol{\mathrm{d}}(B)$), a
$\boldsymbol{\mathrm{d}}$-matching between $A$ and $B$ is an edge-weighted
bipartite graph of $A$ and $B$ such that for each $v\in A\cup B$, the weighted
degree (denoted by $M(v)$) is at most $\boldsymbol{\mathrm{d}}(v)$. The value
of $M$ is the total weight of edges, which is equal to $M(A)=\sum_{v\in
A}M(v)$. We say this matching is perfect if $M(A)=\boldsymbol{\mathrm{d}}(A)$.

Lemma 4.9 follows the analysis in [KKOV07]. Strictly speaking, [KKOV07] only
showed that the cut-matching game on an $n$-vertex unweighted graph has at
most $O(\log n)$ rounds. However, observe that the game on a weighted graph
$H$ can also run on an unweighted graph $H^{\prime}$ in which $w(v)$ copies
are created for each original vertex $v\in V(H)$, so Lemma 4.9 follows.

######  Lemma 4.9.

The number of rounds of the cut-matching game will be at most $O(\log(nU))$.

The Cut Player. We will use the algorithm in Lemma 4.10 from [LS21] to
implement the cut player.

######  Lemma 4.10 (Theorem 2.4 in [LS21]).

Let $H=(V(H),E(H),w_{H},\boldsymbol{\mathrm{d}})$ be an $n$-vertex $m$-edge
graph with integral edge weight $1\leq w_{H}(e)\leq U$ for all $e\in E(H)$ and
integral demand $0\leq d(v)\leq U$ for all $v\in V(H)$. Given a parameter
$r\geq 1$, there is a deterministic algorithm that returns either

  * •

a cut $(A,B)$ in $H$ with
$\boldsymbol{\mathrm{d}}(A),\boldsymbol{\mathrm{d}}(B)\geq\boldsymbol{\mathrm{d}}(V(H))/4$
and $w_{H}(E_{H}(A,B))\leq\boldsymbol{\mathrm{d}}(V(H))/100$; or

  * •

a set $S\subseteq V(H)$ with
$\boldsymbol{\mathrm{d}}(S)\geq\boldsymbol{\mathrm{d}}(V(H))/2$ such that
$\Psi(H[S])\geq 1/\log^{O(r^{4})}m$.

The running time of this algorithm is
$O(m\cdot(mU)^{O(1/r)}\log^{O(r^{2})}(mU))$.

Proposition 4.11 concludes that the game ends with an expander, which is an
easy observation from the fact that in the last round of the game, a large
subgraph $H[S]$ has been an expander by Lemma 4.10 and the matching player
connects vertices in $V(H)\setminus S$ to $S$ by a
$\boldsymbol{\mathrm{d}}$-matching with value $|V(H)\setminus S|$.

######  Proposition 4.11.

If the cut player is implemented by the algorithm in Lemma 4.10 with parameter
$r\geq 1$, the final graph $H$ has sparsity $\Psi(H)\geq 1/\log^{O(r^{4})}m$,
where $m$ is the final number of edges.

The Matching Player. As shown in Section 4.2, in order to solve the most-
balanced sparse vertex cut problem, we will try to embed (see Definition 4.12)
an expander generated by the cut-matching game into the graph $G$ we want to
decompose, and we hope the embedding has low vertex congestion. Since the
expander is the union of a small number of matchings decided by the matching
player, the strategy of the matching player is to somehow compute a matching
and its low-vertex-congestion embedding simultaneously141414To be precise, the
matching player in Lemma 4.13 will compute either a matching which can be
almost embedded into $G$, or some balanced sparse vertex vertex cut. This
suffices to show the result in Section 4.2. in each round. Because the number
of rounds is small, we can simply takes the union of embeddings of matchings
as the desired embedding of the expander.

Analogous to [NS17, CGL+20], we implement the matching player (see Lemma 4.13)
using approximate vertex-capacitated max flow algorithm as a subroutine. We
discuss the approximate vertex-capacitated max flow algorithm in Appendix B
and leave the complete proof of Lemma 4.13 in Section A.2.

######  Definition 4.12 (Embedding).

Let $G=(V(G),E(G),w)$ be a graph with positive integral vertex weights $w$,
and let $H=(V(H),E(H),w_{H})$ be an graph with $V(H)=V(G)$ and positive
integral edge weights $w_{H}$. An embedding of $H$ into $G$ is a collection
${\cal P}$ of unweighted paths in $G$, where for each $e=(u,v)\in E(H)$, there
are exactly $w_{H}(e)$ paths in ${\cal P}$ connecting $u$ and $v$. If there
exists a value $\eta$ such that each vertex $v\in V(G)$ appears in at most
$\eta\cdot w(v)$ paths in ${\cal P}$, we say that the embedding has vertex-
congestion $\eta$. We use $E({\cal P})$ to denote edges in $E(G)$ involved in
${\cal P}$.

######  Lemma 4.13.

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be an $n$-vertex $m$-edge graph
with, for each $v\in V(G)$, integral weights $1\leq w(v)\leq U$ and integral
demands $0\leq\boldsymbol{\mathrm{d}}(v)\leq w(v)$. Let $(A,B)$ be an edge cut
of $G$ with $\boldsymbol{\mathrm{d}}(A)\leq\boldsymbol{\mathrm{d}}(B)$. Given
$z\geq 0,0<\phi\leq 1$, there is a deterministic algorithm that computes

  * •

either a $\boldsymbol{\mathrm{d}}$-matching $M$ between $A$ and $B$ with value
at least $\boldsymbol{\mathrm{d}}(A)-z$ such that there is an embedding ${\cal
P}$ of $M$ into $G$ with vertex-congestion $O(\log(nU)/\phi)$; or

  * •

a vertex cut $(L,S,R)$ in $G$ with
$\boldsymbol{\mathrm{d}}(L),\boldsymbol{\mathrm{d}}(R)>z$ and
$h_{G}(L,S,R)\leq\phi$.

The running time of this algorithm is $O(m^{1+o(1)}U\log U/\phi)$. If the
output is the $\boldsymbol{\mathrm{d}}$-matching $M$, the algorithm can
further output the set $E({\cal P})$ of ${\cal P}$.

###  4.2 Most-Balanced Sparse Vertex Cut

In a most-balanced sparse vertex cut problem, the goal is to compute a sparse
vertex cut $(L,S,R)$ with vertex expansion at most a given parameter $\phi$
such that it is the most-balanced in the sense that the demand of the smaller
side, i.e. $\min\\{\boldsymbol{\mathrm{d}}(L),\boldsymbol{\mathrm{d}}(R)\\}$,
is maximized. This problem in the edge cut setting has been studied in [ST04,
KRV09, NS17, WN17]. As shown in these works, there exists an efficient
approximation algorithm for the bi-criteria decision version of this problem.
By applying the same techniques to the vertex cut setting, we can obtain Lemma
4.14.

######  Lemma 4.14.

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be an $n$-vertex $m$-edge graph
with, for each $v\in V(G)$, integral weight $1\leq w(v)\leq U$ and integral
demand $0\leq\boldsymbol{\mathrm{d}}(v)\leq w(v)$. Given parameters
$0<\phi\leq 1,z\geq 0$ and $r\geq 1$, there is a deterministic algorithm that
either

  * •

returns a vertex cut $(L,S,R)$ of $G$ with
$\boldsymbol{\mathrm{d}}(R)\geq\boldsymbol{\mathrm{d}}(L)>z$ and
$h_{G}(L,S,R)\leq\phi$; or

  * •

certifies that every vertex cut $(L,S,R)$ with $\boldsymbol{\mathrm{d}}(L\cup
S),\boldsymbol{\mathrm{d}}(R\cup S)\geq\alpha z\log U\log^{\alpha r^{4}}(m\log
U)$ has $h_{G}(L,S,R)\geq\phi/(\alpha\log^{2}U\log^{\alpha r^{4}}(m\log U))$,
where $\alpha>0$ is a universal constant.

The running time of this algorithm is $O(m^{1+o(1)+O(1/r)}\cdot
U^{1+O(1/r)}\cdot\log^{O(r^{2})}(mU)/\phi)$.

The key idea is trying to embed an expander into the graph $G$ with low vertex
congestion via the cut-matching game. If we fail to get the embedding because
the matching player throws out a balanced sparse cut in some round, then this
cut is an acceptable output of Lemma 4.14. Otherwise, we hope to get such an
embedding, so that the algorithm can also terminate because intuitively, a
low-vertex-congestion embedding of an expander into $G$ can certify that $G$
is a vertex expander.

However, the matching player in Lemma 4.13 is somewhat weaker. In the latter
case, it only computes in each round a non-perfect (but large) matching
$M_{i}$ embeddable into $G$. Equivalently, if we augment $M_{i}$ into a
perfect matching $M_{i}\cup F_{i}$ by adding some fake edges $F_{i}$, finally
we can only embed a “nearly expander” $\hat{H}=H-F$ into $G$ where
$H=\bigcup_{i}M_{i}\cup F_{i}$ is an expander and $F=\bigcup_{i}F_{i}$ the set
of a small number of fake edges. Fortunately, this suffices to prove Lemma
4.14 because intuitively, all balanced cuts in the “nearly expander” $\hat{H}$
are not sparse, and the low-vertex-congestion embedding of $\hat{H}$ into $G$
can certify that all balanced vertex cuts in $G$ have high vertex expansion as
desired.

Corollary 4.15 is a corollary of Lemma 4.14 where we set the balanced
parameter $z=0$. It will be used in Section 5 as a subroutine. The complete
proof of Lemma 4.14 and Corollary 4.15 is in Section A.3.

######  Corollary 4.15.

Let $G=(V(G),E(G),w,\boldsymbol{\mathrm{d}})$ be an $n$-vertex $m$-edge graph
with, for each $v\in V(G)$, integral weight $1\leq w(v)\leq U$ and integral
$0\leq\boldsymbol{\mathrm{d}}(v)\leq w(v)$. Given parameters $0<\phi\leq 1$,
there is a deterministic algorithm that either

  * •

returns a vertex cut $(L,S,R)$ of $G$ with
$\boldsymbol{\mathrm{d}}(R)\geq\boldsymbol{\mathrm{d}}(L)>0$ and
$h_{G}(L,S,R)\leq\phi$; or

  * •

certifies that there is an embedding ${\cal P}$ of an expander $H$ with the
same demand $\boldsymbol{\mathrm{d}}$ and $\Psi(H)\geq 1/(m\log U)^{o(1)}$
into $G$ with vertex-congestion at most $O(\frac{\log^{2}(nU)}{\phi})$ and
returns the set $E({\cal P})$ of edges involved in this embedding.

The running time of this algorithm is $O(m^{1+o(1)}U^{1+o(1)}/\phi)$.

The remaining proof getting to Lemma 4.6 follow the parameter-adjusting
technique in [NS17], which also appeared in [CGL+20]. The algorithm keep
prunning the graph $G$ using Lemma 4.14 in several phases, and the parameters
$\phi$ and $z$ passed to Lemma 4.14 will change between phases. When the
algorithm terminates, the vertex cut separated the pruned part and the
remaining part is sparse since the graph is pruned by a sparse vertex cut each
time. If the pruned part is large, then we obtain a balanced sparse vertex
cut, otherwise the remaining part is large and it will be certified as an
expander. The complete proof is shown in Section A.4.

##  5 The Low Degree Hierarchy

The low degree hierarchy, which was first introduced in [DP20], is an
important ingredient of our oracle. In this section, we will show an
alternative construction algorithm of the low degree hierarchy, which exploits
vertex expander decomposition. Compared to the construction in [DP20], our
algorithm is more time-efficient, at a cost of giving a slightly low-quality
hierarchy.

In short, the low degree hierarchy includes a laminar set ${\cal C}$ of
components and a set ${\cal T}$ of low-degree Steiner trees. Every component
$\gamma\in{\cal C}$ is corresponding to a tree $\tau\in{\cal T}$ which will
span all (but may not only) terminals of $\gamma$, where terminals of $\gamma$
are vertices in $V(\gamma)$ that are not in any of the child components. The
main result of this section is an almost-linear time construction algorithm
for the low degree hierarchy as shown in Theorem 5.3. In Section 5.1, we will
show how to use vertex expander decomposition repeatedly to construct a
prototype of the low degree hierarchy. In Section 5.2, we will refine the
prototype to formally construct the hierarchy and complete the proof of
Theorem 5.3.

######  Definition 5.1 (Low Degree Hierarchy).

Let $G$ be a connected undirected graph. A $(p,\Delta)$-low degree hierarchy
with height $p$ and degree parameter $\Delta$ on $G$ is a pair $({\cal
C},{\cal T})$ of sets, where ${\cal C}$ is a set of vertex-induced connected
subgraphs called components, and ${\cal T}$ is a set of Steiner trees with
maximum vertex degree at most $\Delta$.

The set ${\cal C}$ of components is a laminar set. Specifically, ${\cal C}$
has the following properties.

  * (1)

Components in ${\cal C}$ belong to $p$ levels and we denote by ${\cal C}_{i}$
the set of components at level $i$. In particular, at the top level $p$,
${\cal C}_{p}=\\{G\\}$ is a singleton set with the whole $G$ as the unique
component. Furthermore, for each level $i\in[1,p]$, components in ${\cal
C}_{i}$ are vertex-disjoint and there is no edge in $E(G)$ connecting two
components in ${\cal C}_{i}$.

  * (2)

For each level $i\in[1,p-1]$ and each component $\gamma\in{\cal C}_{i}$, there
is a unique component $\gamma^{\prime}\in{\cal C}_{i+1}$ such that
$V(\gamma)\subseteq V(\gamma^{\prime})$, where we say that $\gamma^{\prime}$
is the parent-component of $\gamma$ and that $\gamma$ is a child-component of
$\gamma^{\prime}$.

  * (3)

For each component $\gamma\in{\cal C}$, the terminals of $\gamma$, denoted by
$U(\gamma)$, are vertices in $\gamma$ but not in any of $\gamma$’s child-
components. Note that $U(\gamma)$ can be empty. In particular, for each
$\gamma\in{\cal C}_{1}$, $U(\gamma)=V(\gamma)$.

Generally, for each level $i\in[1,p]$, we define the terminals at level $i$ be
terminals in all components in ${\cal C}_{i}$, denoted by
$U_{i}=\bigcup_{\gamma\in{\cal C}_{i}}U(\gamma)$.

The set ${\cal T}$ of low-degree Steiner trees has the following properties

  * (4)

${\cal T}$ can also be partitioned into subsets ${\cal T}_{1},...,{\cal
T}_{p}$, where ${\cal T}_{i}$ denote trees at level $i$ and trees in ${\cal
T}_{i}$ are vertex-disjoint.

  * (5)

For each level $i\in[1,p]$ and tree $\tau\in{\cal T}_{i}$, the terminals of
$\tau$ is defined by $U(\tau)=U_{i}\cap V(\tau)$.

  * (6)

For each level $i\in[1,p]$ and each component $\gamma\in{\cal C}_{i}$ with
$U(\gamma)\neq\emptyset$, there is a tree $\tau\in{\cal T}_{i}$ such that
$U(\gamma)\subseteq U(\tau)$, denoted by $\tau(\gamma)$. We emphasize that two
different components $\gamma$ and $\gamma^{\prime}\in{\cal C}_{i}$ may
correspond to the same tree $\tau\in{\cal T}_{i}$.

######  Proposition 5.2.

In Definition 5.1, terminal sets of components $\\{U(\gamma)\mid\gamma\in{\cal
C}\\}$ forms a partition of $V(G)$. Similarly, regarding terminal sets of
Steiner trees and levels, $\\{U(\tau)\mid\tau\in{\cal T}\\}$ and $\\{U_{i}\mid
1\leq i\leq p\\}$ are also partitions of $V(G)$.

The main result of this section is Theorem 5.3. As a comparison, we state the
result of [DP20] in Theorem 5.4. Combining new algorithms in the following
sections, we can get some tradeoffs on complexity measures of our final
oracles by choosing the construction algorithm of the low degree hierarchy.

######  Theorem 5.3.

Given an $n$-vertex $m$-edge graph $G$, there is a deterministic algorithm to
construct the low degree hierarchy $({\cal C},{\cal T})$ with $p=O(\beta(n))$
levels and degree parameter $\Delta=n^{o(1)}$, where $\beta(n)$ is any slowly
growing function e.g. $\beta(n)=\log^{*}n$. The running time of this algorithm
is $m^{1+o(1)}$ and the space to store the hierarchy explicitly is
$O(pm)=O(m\cdot\beta(n))$.

######  Theorem 5.4 ([DP20]).

Given an $n$-vertex $m$-edge graph $G$, there is a deterministic algorithm to
construct the low degree hierarchy $({\cal C},{\cal T})$ with $p=O(\log n)$
levels and degree parameter $\Delta=4$. The running time of this algorithm is
$O(mn\log n)$ and the space to store the hierarchy explicitly is $O(m\log n)$.

###  5.1 Repeated Vertex Expander Decomposition

In this subsection, we will design an algorithm which takes the graph $G$ as
the input and output a repeated vertex expander decomposition of $G$, which
serves as a prototype of the hierarchy. In our algorithm, we will view
Corollary 4.4 as a subroutine which computes a “terminal version” of
unweighted vertex expander decomposition, in which the vertex expansion is
with respect to a given terminal set $T$ (see Definition 5.5).

######  Definition 5.5 (Vertex Expansion with respect to Terminals).

Let $G$ be an unweighted graph with a terminal set $T\subseteq V(G)$. For each
vertex cut $(L,S,R)$ of $G$ with $|(L\cup S)\cap T|,|(R\cup S)\cap T|>0$, its
vertex expansion with respect to $T$ is $h_{G,T}(L,S,R)=|S|/\min\\{|(L\cup
S)\cap T|,|(R\cup S)\cap T|\\}$. The vertex expansion of $G$ with respect to
$T$, denoted by $h(G,T)$, is the minimum $h_{G,T}(L,S,R)$ of any vertex cut
$(L,S,R)$ with $|(L\cup S)\cap T|,|(R\cup S)\cap T|>0$.

Note that Definition 5.5 is equivalent to the notion of vertex expansion in
Definition 4.1 if we extend $G$ to a weighted graph with weight function $w$
and demand function $\boldsymbol{\mathrm{d}}_{T}$ as follows. For each vertex
$v\in V(G)$, it has weight $w(v)=1$. For a given $T$, each vertex in $T$ has
demand $\boldsymbol{\mathrm{d}}_{T}=1$ and each vertex in $V(G)\setminus T$
has demand $\boldsymbol{\mathrm{d}}_{T}=0$.

Let $\beta(n)\leq\log n$ be any slowly growing function. The algorithm is
iterative. We let $T_{i}$ denote the terminals of the $i$-th iteration with
$T_{1}=V(G)$ initially. In the $i$-th iteration, we apply Corollary 4.4 (the
deterministic version) on graph $G$ with weight function $w$, demand function
$\boldsymbol{\mathrm{d}}_{T_{i}}$ and parameter
$\epsilon=n^{1/\beta(n)}=n^{o(1)}$, which will return a decomposition ${\cal
G}_{i}$. The terminal set $T_{i+1}$ for the next iteration is the vertices
dropped in this decomposition, i.e.
$T_{i+1}=V(G)\setminus\left(\bigcup_{V_{j}\in{\cal G}_{i}}V_{j}\right)$. We
proceed to the next iteration unless $T_{i+1}=\emptyset$. Let $p$ denote the
number of iterations. The outputs are $T_{1},...,T_{p}$ and ${\cal
G}_{1},...,{\cal G}_{p}$ with properties summarized in Lemma 5.6.

######  Lemma 5.6.

Given an $n$-vertex $m$-edge graph $G$, there is a deterministic algorithm
that computes $T_{1},...,T_{p}$ and ${\cal G}_{1},...,{\cal G}_{p}$ with
$p=O(\beta(n))$ and the following properties.

  * (1)

For each $1\leq i\leq p-1$, $T_{i+1}=V(G)\setminus\left(\bigcup_{V_{j}\in{\cal
G}_{i}}V_{j}\right)$. In particular, $T_{1}=V(G)$.

  * (2)

For each $1\leq i\leq p$ and any two distinct $V_{j},V_{j^{\prime}}\in{\cal
G}_{i}$, $V_{j}$ and $V_{j^{\prime}}$ are disjoint and there is no edge in
$E(G)$ connecting a vertex in $V_{j}$ and another vertex in $V_{j^{\prime}}$.

  * (3)

For each $1\leq i\leq p$ and $V_{j}\in{\cal G}_{i}$, the vertex expansion of
$G[V_{j}]$ with respect to $V_{j}\cap T_{i}$ is at least $1/n^{o(1)}$.

The running time of this algorithm is $m^{1+o(1)}$.

###### Proof.

First we claim that $p=O(\beta(n))$ because in every iteration $i$, we have
$|T_{i+1}|=w(V(G)\setminus(\bigcup_{V\in{\cal
G}_{i}}V))\leq\epsilon\cdot\boldsymbol{\mathrm{d}}_{T_{i}}(V(G))=|T_{i}|/n^{1/\beta(n)}$
by Corollary 4.4. The property (1) is directly from the algorithm, and
properties (2) and (3) are from Corollary 4.4. Furthermore, each iteration
takes $m^{1+o(1)}$ time to apply Corollary 4.4 once, so the total running time
is $m^{1+o(1)}$.

∎

###  5.2 Construction

We now formally construct the low degree hierarchy. The key relation between
the repeated vertex expander decomposition and the low degree hierarchy is
shown in Lemma 5.7. Roughly speaking, a graph with high vertex expansion with
respect to a terminal set contains a low degree Steiner tree spanning all
terminals.

######  Lemma 5.7.

Let $G$ be an $n$-vertex $m$-edge graph with a terminal set $T\subseteq V(G)$.
If $h(G,T)$ is at least $\phi$, there is a deterministic algorithm that
computes a Steiner tree $\tau$ in $G$ spanning $T$ with maximal vertex degree
at most $O(\frac{\log^{2}n}{\phi})$. The running time of this algorithm is
$m^{1+o(1)}/\phi$.

###### Proof.

We apply Corollary 4.15 to the graph
$G=(V(G),E(G),w_{1},\boldsymbol{\mathrm{d}}_{T})$ with parameter $\phi/2$.
Because the weighted vertex expansion $h(G)$ is exactly $h(G,T)\geq\phi$,
Corollary 4.15 must certify that we can embed an expander $H$ with the same
demand $\boldsymbol{\mathrm{d}}_{T}$ into $G$ with vertex-congestion
$\eta=O(\log^{2}n/\phi)$ and return $E({\cal P})$ of this embedding ${\cal
P}$. Let $\tau^{\prime}$ be the graph with $V(\tau^{\prime})=V(G)$ and
$E(\tau^{\prime})=E({\cal P})$. Because $H$ is an expander where each $v\in T$
has demands $\boldsymbol{\mathrm{d}}_{T}=1$, by the definition of embedding,
vertices in $T$ must be connected in $\tau^{\prime}$ (although $\tau^{\prime}$
itself may not be a connected graph). Moreover, the maximum vertex degree in
$\tau^{\prime}$ is at most $\eta=O(\log^{2}n/\phi)$. Therefore, in the
spanning forest of $\tau^{\prime}$, there must be a tree $\tau$ spanning all
vertices in $T$. The running time is $m^{1+o(1)}/\phi$ taken by Corollary 4.15
and the other parts take nearly linear time. ∎

Given the outputs $T_{1},...,T_{p}$ and ${\cal G}_{1},...,{\cal G}_{p}$ of
Lemma 5.6, the construction algorithm is as follows.

  * (A)

The hierarchy has $p$ levels. For each level $i$, the terminals at this level
are $U_{i}=T_{i}\setminus\bigcup_{i^{\prime}=i+1}^{p}T_{i^{\prime}}$.

  * (B)

For each level $i\in[1,p]$, the set ${\cal T}_{i}$ of low-degree Steiner trees
is constructed as follows. For each $V_{j}\in{\cal G}_{i}$, by applying Lemma
5.7 on $G[V_{j}]$ with terminal set $V_{j}\cap T_{i}$, we can obtain a Steiner
tree $\tau_{i,j}$ in $G[V_{j}]$ spanning $V_{j}\cap T_{i}$ with maximal vertex
degree $n^{o(1)}$ since $h(G[V_{j}],V_{j}\cap T_{i})\geq 1/n^{o(1)}$. The set
${\cal T}_{i}$ will collect all such $\tau_{j}$, i.e. ${\cal
T}_{i}=\\{\tau_{i,j}|V_{j}\in{\cal G}_{i}\\}$, where each $\tau_{i,j}$ has
terminals $U(\tau_{i,j})=V_{j}\cap U_{i}$. The whole set ${\cal
T}=\bigcup_{i=1}^{p}{\cal T}_{i}$.

  * (C)

For each level $i\in[1,p]$, the set ${\cal C}_{i}$ of components collect all
connected components of the graph
$G\setminus\bigcup_{i^{\prime}=i+1}^{p}U_{i^{\prime}}$. For each
$\gamma\in{\cal C}_{i}$, its terminals are $U(\gamma)=U_{i}\cap V(\gamma)$.
The whole set ${\cal C}=\bigcup_{i=1}^{p}{\cal C}_{i}$.

######  Lemma 5.8.

The $(\cal C,\cal T)$ constructed above is a low-degree hierarchy with
$p=O(\beta(n))$ levels and degree parameter $r=n^{o(1)}$.

###### Proof.

Properties (1) and (2) in Definition 5.1 are directly from the step (C).
Property (3) follows step (C) and that $\\{U_{1},\cdots,U_{p}\\}$ constructed
above is a partition of $V(G)$, where the latter is from $T_{1}=V(G)$ and step
(A). Property (4) holds because of step (B) and that subgraphs in ${\cal
G}_{i}$ are vertex-disjoint for each level $i$. Regarding property (5), notice
that each $\tau_{i,j}\in{\cal T}_{i}$ corresponding to some $V_{j}\in{\cal
G}_{i}$ will span $V_{j}\cap T_{i}$, so $U(\tau_{i,j})=V_{j}\cap
U_{i}\subseteq V_{j}\cap T_{i}\subseteq V(\tau_{i,j})$, which implies
$U(\tau_{i,j})=V(\tau_{i,j})\cap U_{i}$. It remains to show property (6).

Consider some level $i$. Each $\gamma\in{\cal C}_{i}$ must be totally
contained by some $V_{j}\in{\cal G}_{i}$, because
$G\setminus(U_{i+1}\cup\cdots\cup U_{p})\subseteq V(G)\setminus
T_{i+1}=\bigcup_{V_{j}\in{\cal G}_{i}}V_{j}$ by (1) in Lemma 5.6 and there is
no edge connecting two distinct $V_{j},V_{j^{\prime}}\in{\cal G}_{i}$ by (2)
in Lemma 5.6. Therefore, $U(\gamma)=V(\gamma)\cap U_{i}\subseteq V_{j}\cap
U_{i}=U(\tau_{i,j})$ as desired. ∎

###### Proof of Theorem 5.3.

The correctness is from Lemma 5.8, and we analyse the running time below. We
first invoke the algorithm in Lemma 5.6, which takes $m^{1+o(1)}$ time.
Consider the algorithm in this subsection. Observe that steps (A) and (C) only
take $\tilde{O}(m)$ time. About step (B), applying Lemma 5.7 on $G[V_{j}]$ for
all $V_{j}\in{\cal G}_{i}$ takes $m^{1+o(1)}$ time for each level $i$. Summing
over $p=O(\beta(n))\leq O(\log n)$ levels, step (B) takes totally $m^{1+o(1)}$
time. Thus the total running time is $m^{1+o(1)}$. ∎

##  6 The Affiliated Structures

In this section, we will construct some affiliated structures to augment the
low degree hierarchy. Before introducing the affiliated structures, we first
discuss in Section 6.1 how we react against a set $D$ of failed vertices by
exploiting a $(p,\Delta)$-low degree hierarchy. Basically, given a failure set
$D$, we will reduce the original graph to a semi-bipartite graph called the
abstract graph. The overview of affiliated structures is shown in Section 6.2.

###  6.1 The Abstract Graph $H$ for a Failure Set $D$

Let $D$ be a set of failed vertices with $|D|=d\leq d_{\star}$. After
failures, some objects in the low degree hierarchy still provide valid
information on connectivity.

We first focus on components. We call some $\gamma\in{\cal C}$ an unaffected
component if $V(\gamma)\cap D=\emptyset$, otherwise we call $\gamma$ an
affected component. because an unaffected component $\gamma$ does not involve
any failed vertex, it certifies that vertices in $V(\gamma)$ are still
connected in graph $G\setminus D$. By the laminar property of ${\cal C}$, it
is enough to consider maximal unaffected components, which is defined as an
unaffected component with an affected component as the parent-component. We
let all maximal unaffected components be the first-type objects. When we are
solving the connectivity of $G\setminus D$, we can view vertices in each
first-type object as a whole.

The remaining vertices which cannot be grouped by first-type objects are
exactly the non-failed terminals of affected components, because the terminal
sets of components partition $V(G)$ and for each first-type object $\gamma$,
$V(\gamma)$ is exactly the union of terminal sets of its descendant
components. Recall that for each affected component $\gamma\in{\cal C}$, its
terminals $U(\gamma)$ are contained in a single tree $\tau(\gamma)\in{\cal T}$
if $U(\gamma)\neq\emptyset$ (see (6) in Definition 5.1 for details) and we
call this tree an affected tree. Although an affected tree may be split by
failed vertices into several subtrees (called affected subtrees) in
$G\setminus D$, the total number of affected subtrees will not be large by the
low-degree property of trees in ${\cal T}$. We let all affected subtrees be
the second-type objects, and for each affected subtree $\hat{\tau}$ of an
affected tree $\tau$, we define the terminal set of $\hat{\tau}$ as
$U(\hat{\tau})=U(\tau)\cap V(\hat{\tau})$. Similarly, for each affected
subtree, we can group as a whole its terminals not in any of first-type
objects151515Some vertex in $U(\hat{\tau})$ can be inside some first-type
object because $U(\hat{\tau})$ may contain terminals of several components
(see (6) of Definition 5.1). Indeed we can group all vertices inside an
affected subtree as a whole since this tree is connected in $G\setminus D$.
Here we only group a part of vertices because for simplicity, we want all
groups form a partition of $V(G)\setminus D$..

######  Definition 6.1.

We define the abstract graph $H$ for $D$ as follows.

  * •

Let $\hat{\cal C}$ denote the set of first-type objects and $\hat{\cal T}$
denote the set of second-type objects. Then $V(H)=\hat{\cal C}\cup\hat{\cal
T}$, which means vertices in $V(H)$ one-one correspond to objects. Without
ambiguity, we use the same notation $\gamma\in\hat{\cal C}$ (resp.
$\hat{\tau}\in\hat{\cal T}$) to denote both the first-type object (resp. the
second-type object) and its corresponding vertex in $V(H)$.

  * •

Each vertex in $V(H)$ is an abstraction of a subset of $V(G)\setminus D$,
where all subsets form a partition of $V(G)\setminus D$. Specifically, for
each vertex $\gamma\in\hat{\cal C}$, it represents $g^{-1}(\gamma)=V(\gamma)$,
while for each vertex $\hat{\tau}\in\hat{\cal T}$, it represents
$g^{-1}(\hat{\tau})=U(\hat{\tau})\setminus\bigcup_{\gamma\in\hat{\cal
C}}V(\gamma)$. We assume that each $\hat{\tau}\in\hat{\cal T}$ has nonempty
$g^{-1}(\hat{\tau})$ by ignoring those $\hat{\tau}$ with empty
$g^{-1}(\hat{\tau})$.

We have $\\{g^{-1}\\}_{v_{H}\in V(H)}$ is a partition of $V(G)$ by the
discussion above, so we can define a mapping $g:V(G)\to V(H)$ by defining
$g(v)$ be the unique $v_{H}$ such that $v\in g^{-1}(v_{H})$ for each $v\in
V(G)$.

  * •

The edge set $E(H)=\\{(g(u),g(v))\mid(u,v)\in E(G)\\}$ is a multiset of edges
one-one correspond to edges in $E(G\setminus D)$, where each edge $(u,v)\in
E(G\setminus D)$ is mapped to an edge $(g(u),g(v))\in E(H)$.

######  Lemma 6.2.

Given a failure set $D$ with $|D|=d$, the abstract graph $H$ has the following
properties.

  * (1)

The number of second-type objects is $O(pd\Delta)$.

  * (2)

There is no edge connecting two first-type objects.

  * (3)

For any two second-type objects $\hat{\tau}_{1}$ and $\hat{\tau}_{2}$,
$\hat{\tau}_{1}$ and $\hat{\tau}_{2}$ is connected in $H$ if some $v_{1}\in
V(\hat{\tau}_{1})$ and $v_{2}\in V(\hat{\tau}_{2})$ is connected in
$G\setminus D$, and any $v_{1}\in V(\hat{\tau}_{1})$ and $v_{2}\in
V(\hat{\tau}_{2})$ is connected in $G\setminus D$ if $\hat{\tau}_{1}$ and
$\hat{\tau}_{2}$ is connected in $H$.

###### Proof.

Because components in the same level are disjoint by (1) in Definition 5.1,
there are at most $O(d)$ affected trees in each level, so the total number of
affected trees is $O(pd)$. Because affected trees at the same level are
disjoint by (4) in Definition 5.1, there are totally $O(pd)$ failed vertices
on affected trees summing over $p$ levels. Furthermore, each affected tree has
maximum vertex degree $\Delta$, so the number of affected subtrees (namely
second-type objects) is $O(pd\Delta)$.

Let $\gamma_{1},\gamma_{2}$ be two distinct first-type objects and assume
$\gamma_{1}$ is at a higher level (or the same level) than $\gamma_{2}$. By
(2) in Definition 5.1, $\gamma_{2}$ has a unique ancestor
$\gamma^{\prime}_{2}$ at the same level with $\gamma_{1}$, such that
$V(\gamma_{2})\subseteq V(\gamma^{\prime}_{2})$ and there is no edge
connecting $\gamma_{1}$ and $\gamma^{\prime}_{2}$. Thus property (2) follows.

Note that each second-type object $\hat{\tau}$ has nonempty
$g^{-1}(\hat{\tau})$. Then property (3) follows the facts that each affected
subtree is a connected subgraph of $G\setminus D$ and the transformation from
$G\setminus D$ to $H$ preserves connectivity. ∎

The task of our update algorithm is to compute the connectivity of the
abstract graph $H$. Precisely, since the number of first-type objects may be
large but the number of second-type objects is quite small by (1), we will see
that, our update algorithm only reestablish connectivity among second-type
objects in $H$. The data structures constructed in this section aim for
supporting fast update algorithm.

###  6.2 Overview

There are two parts of the affiliated structures. The first part is basically
a 2D range counting structure in Section 6.3. The intuition behind is that we
can view affected subtrees, i.e. the second-type objects, as intervals on some
Euler tour order by Lemma 6.3, so querying whether two affected subtrees are
connected directly by some edges is equivalent to some 2D range counting
queries.

An issue is that two second-type objects in $H$ can be connected by, instead
of an edge, a path through a first type object, but such paths are not
captured by a 2D range counting structure only storing original edges.
Following an idea from [DP20], we will add artificial edges into the counting
structure to capture the connectivity provided by them. Our construction of
artificial edges in Section 6.4 is deterministic and compact, which leads to
faster deterministic update algorithm and lower space requirement.

Since the objects of $H$ are “dynamic” (depending on $D$), we should be able
to efficiently “subtract” from the 2D range counting structure artificial
edges whose underlying paths go through affected components, because these
edges are not guaranteed to provide valid connectivity. Therefore, we also
construct some navigation structures around artificial edges in Section 6.4.
When some components becomes affected, these structures can support efficient
“subtraction” of invalid artifical edges.

###  6.3 The Euler Tour Order and the 2D Range Counting Structure

Our goal of this subsection is to construct a 2D range counting structure (see
Lemma 6.5) to support connectivity queries of affected subtrees under a
multiset of edges $E=E(G)+\hat{E}$, where $\hat{E}$ is the multiset of
artificial edges which will be constructed in Section 6.4. We emphasize that
although we conceptually define $E$ and $\hat{E}$ be multisets of undirected
edges, actually our algorithm will construct and view them as multisets of
ordered pairs, where each pair relates to an undirected edge. The original
edge set $E(G)$ can also be viewed as a set of ordered pair by giving an
arbitrary direction to each undirected edge.

We will exploit the Euler tour order as in [DP20] to reduce queries on
connectivity of affected subtrees to 2D range counting queries. Our algorithm
will process each $\tau\in{\cal T}$ individually. For an unrooted tree $\tau$,
by picking a root arbitrarily, we define the Euler tour order
$\mathrm{ET}(\tau)$ as an ordered list of the vertices ordered by the time
each vertex first appears during an Euler tour of $\tau$ (treating each
undirected edge as two directed edges). The Euler tour order can be
interpreted as a linearization of the tree in the sense that after deleting
some vertices on $\tau$, the remaining subtrees are corresponding to intervals
in $\mathrm{ET}(\tau)$ as shown in Lemma 6.3. Proving Lemma 6.3 is an easy
exercise and we leave the complete proof in Section A.5.

######  Lemma 6.3.

Let $\tau$ be an undirected tree with maximum vertex degree $\Delta$. A
removal of $d$ failed vertices from $\tau$ will split $\tau$ into at most
$O(\Delta d)$ subtrees
$\hat{\tau}_{1},\hat{\tau}_{2},\cdots,\hat{\tau}_{O(\Delta d)}$, and there
exists a set $I_{\tau}$ of at most $O(\Delta d)$ disjoint intervals on
$\mathrm{ET}(\tau)$, such that each interval is owned by a unique subtree and
for each subtree $\tau_{i}$, $V(\tau_{i})$ is equal to the union of intervals
it owns.

Furthermore, by preprocessing $\tau$ in $O(|V(\tau)|)$ time, given any set of
$d$ failed vertices, after $O(\Delta d\log(\Delta d))$ update time, these
intervals (with the owner of each of them) can be computed and any query on
which subtree contains a given vertex can be answered in $O(\log d)$ query
time.

As mentioned in Section 6.1, each affected subtree $\hat{\tau}\in V(H)$ serves
as an abstraction of vertices in $g^{-1}(\hat{\tau})$ which is a subsets of
its terminal set $U(\hat{\tau})$. Therefore, we define the global Euler tour
order by focusing on terminals of trees in ${\cal T}$, and take it as indices
of the 2D range counting structure in Lemma 6.5. We note that the global Euler
tour order is a permutation of $V(G)$ since $\\{U(\tau)\mid\tau\in{\cal T}\\}$
is a partition of $V(G)$ as shown in Proposition 5.2.

######  Definition 6.4 (Global Euler Tour Order).

For each level $i$ and each $\tau\in{\cal T}_{i}$, we treat its terminal set
$U(\tau)$ as an ordered list ordered by $\mathrm{ET}(\tau)$. The global Euler
tour order $\mathrm{ET}_{\mathrm{glo}}$ is the concatenation of $U(\tau)$ for
all $\tau\in{\cal T}$ in an arbitrary order. For each vertex $v\in V(G)$, we
let $\mathrm{Id}(v)$ be an integer in $[1,n]$ which denotes the rank of $v$ in
$\mathrm{ET}_{\mathrm{glo}}$.

######  Lemma 6.5 (2D Range Counting Structure).

Let $E$ be a multiset of ordered pairs in $V(G)\times V(G)$. There is a data
structure which given any disjoint intervals $I_{1},I_{2}$ on
$\mathrm{ET}_{\mathrm{glo}}$, can answer in $O(\log n)$ time the number of
pairs in $E$ with first entries in $I_{1}$ and second entries in $I_{2}$,
namely $|E\cap(I_{1}\times I_{2})|$. The data structure takes space is
$O(\|E\|_{0}\log n)$ and the construction time is $O(|E|\log n)$, where
$\|E\|_{0}$ denote the number of distinct elements in $E$.

###### Proof.

We can generate from $E$ a weighted 2D point set $Q$ with $|Q|=\|E\|_{0}$ by
putting for each $(u,v)\in E$, a point $(\mathrm{Id}(u),\mathrm{Id}(v))$ to
$Q$ weighted by the number of $(u,v)$ in $E$. This step takes $O(|E|\log n)$
time via sorting. Then the problem is reduced to a standard weighted 2D range
counting problem. It can be solved by textbook algorithms e.g. the range tree
[Ben80] or the persistent segment tree [DSST89, BW80]. The space is
$O(|Q|\log|Q|)=O(\|E\|_{0}\log n)$ and the query time is $O(\log n)$. ∎

######  Remark 6.6.

There are linear-space data structures for weighted 2D range counting problem.
For example, for a set $Q$ of weighted 2D points, the semigroup range
searching data structure161616It even works for a stronger setting that the
weights are in a semigroup. in [Cha88] takes $O(|Q|\log|Q|)$ preprocessing
time and $O(|Q|)$ space and achieves $O(\log^{2+\epsilon}|Q|)$ query time for
any constant $\epsilon>0$. Using such data structures for Lemma 6.5 will
improve the space of our oracle by an $O(\log n)$ factor, but will increase
the update time by a factor $O(\log^{1+\epsilon}n)$.

###  6.4 Artificial Edges

In this subsection, we will construct the set $\hat{E}$ of artificial edges.
Actually, our algorithm will construct a set $\hat{E}_{\gamma}$ of artificial
edges for each $\gamma\in{\cal C}$, in which each artificial edge will connect
two vertices adjacent to $\gamma$, i.e. the set $\hat{E}_{\gamma}$ of ordered
pairs is a subset of $A_{\gamma}\times A_{\gamma}$, where $A_{\gamma}$ is
$\gamma$’s adjacency list (see Definition 6.7). The whole set $\hat{E}$ is a
multiset such that $\hat{E}=\sum_{\gamma\in{\cal C}}\hat{E}_{\gamma}$.

######  Definition 6.7 (Adjacency List).

For each $\gamma\in{\cal C}$, the adjacency list of $\gamma$ is an ordered
list

$A_{\gamma}=\\{v\mid v\notin V(\gamma)\text{ s.t. }\exists u\in
V(\gamma),(u,v)\in E(G)\\},$

whose order is consistent with $\mathrm{ET}_{\mathrm{glo}}$.

######  Proposition 6.8.

The total size of adjacency lists of all components is $\sum_{\gamma\in{\cal
C}}|A_{\gamma}|=O(pm)$.

###### Proof.

Consider a level $i$ in the low degree hierarchy. For each $\gamma\in{\cal
C}_{i}$ and $v\in A_{\gamma}$, there is an edge connecting $\gamma$ and $v$.
Also, each edge will correspond to at most one such pair of $\gamma$ and $v$
since property (1) in Definition 5.1. Thus $\sum_{\gamma\in{\cal
C}_{i}}|A_{\gamma}|\leq m$ and $\sum_{\gamma\in{\cal C}}|A_{\gamma}|=O(pm)$. ∎

Our update algorithm will only solve the connectivity of second-type objects
in $H$ for efficiency. Recall that there is no edge in $H$ connecting two
different first-type objects (see (2)). Therefore, from the perspective of
second-type objects, each first-type object $\gamma$ with its adjacent edges
can be viewed as a hyperedge, which will also contribute to the connectivity
of second-type objects in addition to original edges. The artificial edges
$\hat{E}_{\gamma}$ of $\gamma$ are served as a simulation of this hyperedge.
Therefore, we hope each $\hat{E}_{\gamma}$ has the following fault-tolerant
property: for any failure set $D$ with $|D|\leq d_{\star}$, there will be
either $A_{\gamma}\subseteq D$ or vertices in $A_{\gamma}\setminus D$ are
connected by $\hat{E}_{\gamma}$. On the other hand, we hope the size of
$\hat{E}_{\gamma}$ is small to save the space taken by the 2D range counting
structure. A natural idea is to take an arbitrary subset $B_{\gamma}\subseteq
A_{\gamma}$ with size $|B_{\gamma}|=d_{\star}+1$ ($B_{\gamma}=A_{\gamma}$ if
$|A_{\gamma}|\leq d_{\star}$), and let $\hat{E}_{\gamma}=A_{\gamma}\times
B_{\gamma}$ with $|\hat{E}_{\gamma}|=O(d_{\star}|A_{\gamma}|)$. This simple
construction can indeed lead to an oracle that takes space
$\tilde{O}(d_{\star}m)$. Actually, this is the optimal construction of
$\hat{E}_{\gamma}$ under this setting by the fact that any $d_{\star}$-vertex-
connected graph on $A_{\gamma}$ has at least $\Omega(d_{\star}|A_{\gamma}|)$
edges.

In our construction, we get around this barrier by slightly relax the
requirement on the fault-tolerant property, inspired by the Monte Carlo
construction algorithm in [DP20]. For each $\gamma\in{\cal C}$, instead of
ensuring the fault-tolerant property on all $\hat{E}_{\gamma}$ in the
preprocessing phase, we are allowed to add some $D$-repairing edges
$\hat{F}_{\gamma}$ temporarily in the update phase, such that
$\hat{E}_{\gamma}\cup\hat{F}_{\gamma}$ is fault-tolerant. Under this setting,
we are able to deterministically construct artificial edges $\hat{E}_{\gamma}$
for each $\gamma\in{\cal C}$ such that the total number of distinct artificial
edges is bounded by $\tilde{O}(m)$, which is exactly nearly linear to the
space of the 2D range counting structure. Moreover, we will show that the
construction of $D$-repairing edges only takes $\tilde{O}(d^{2})$ time and the
total number of $D$-repairing edges is bounded by $\tilde{O}(d^{2})$, which
can be afforded by the update algorithm. Lastly, our construction of
$\hat{E}_{\gamma}$ is based on a simple recursive division on the list
$A_{\gamma}$ called segmentation hierarchy, so the artificial edges are well-
structured and can be efficiently manipulated by the update algorithm.

######  Definition 6.9 (Segmentation Hierarchy).

For each component $\gamma\in{\cal C}$, we define a segmentation hierarchy
${\cal S}_{\gamma}$ on its adjacency list $A_{\gamma}$. ${\cal S}_{\gamma}$ is
an ordered list of segments on $A_{\gamma}$, where a segment on $A_{\gamma}$
is a consecutive sublist of $A_{\gamma}$.

There are $r=\lceil\log|A_{\gamma}|\rceil+1$ levels in the hierarchy and we
denote by ${\cal S}_{\gamma,j}$ the ordered list of segments at level $j$ for
each $1\leq j\leq r$. The whole list ${\cal S}_{\gamma}$ is the concatenation
of ${\cal S}_{\gamma,1},...,{\cal S}_{\gamma,r}$. The list ${\cal
S}_{\gamma,j}$ is obtained by partitioning $A_{\gamma}$ into segments using
step length $2^{j-1}$. Concretely, Let $A_{\gamma}[k_{1},k_{2}]$ denote the
sublist of $A_{\gamma}$ from rank $k_{1}$ to $k_{2}$.

  * •

For $1\leq i\leq\lfloor|A_{\gamma}|/2^{j-1}\rfloor$, the $i$-th segment
$S_{j,i}$ of ${\cal S}_{\gamma,j}$ is $A_{\gamma}[2^{j-1}(i-1)+1,2^{j-1}i]$.

  * •

If $|A_{\gamma}|$ is not divisible by $2^{j-1}$, we let the tail
$A_{\gamma}[2^{j-1}(i-1)+1,|A_{\gamma}|]$ be the last segment $S_{j,i}$ where
$i=\lfloor|A_{\gamma}|/2^{j-1}\rfloor+1$.

Observe that the total number of segments is $|{\cal
S}_{\gamma}|=O(|A_{\gamma}|)$, and the total length of segments is
$O(|A_{\gamma}|\log|A_{\gamma}|)$.

For each segment $S_{j,i}$ $(j\geq 2)$ in the hierarchy, we let $S_{j-1,2i-1}$
and $S_{j-1,2i}$ be its child-segments (the latter may not exist), and we say
$S_{j,i}$ is the parent-segment of $S_{j-1,2i-1}$ and $S_{j-1,2i}$. Observe
that $S_{j,i}$ is exactly the union of its child-segments. In particular, the
topmost level $S_{\gamma,r}$ only contains $A_{\gamma}$ as its unique segment,
called the root segment of this hierarchy.

######  Remark 6.10.

For simplicity, the segmentation hierarchy defined in Definition 6.9 is a two-
branched recursive division with $O(\log n)$ levels. It is natural to define
multiple-branched segmentation hierarchy to obtain a tradeoff between the
number of levels and the number of branches. The number of levels will affect
the space of the oracle, while the number of branches will affect the number
of $D$-repairing edges and the update time. Therefore, when we allow a update
time of $d^{2}n^{o(1)}$, we can use a $n^{o(1)}$-branched segmentation
hierarchy with $\beta(n)$ levels, where $\beta(n)$ is any slowly growing
function e.g. $\beta(n)=\log^{*}n$, which can substitute a $O(\log n)$ factor
in the space complexity by $O(\beta(n))$.

Construction of Artificial Edges. The construction algorithm of all
$\hat{E}_{\gamma}$ will maintain a 2-dimensional labeling table on $V(G)\times
V(G)$, in which all entries are unlabeled initially. In fact, the labeling
table are maintained implicitly by storing all labeled entries in a binary
search tree in order to save the space. We will process components one by one
in an arbitrary order. Let $\gamma$ be the current component.

  * (1)

Let $v_{1},...,v_{|A_{\gamma}|}$ be vertices in $A_{\gamma}$ in order. We let
$b_{\gamma}\leq\min\\{|A_{\gamma}|,d_{\star}+1\\}$ be the smallest integer
such that there are at least $|{\cal S}_{\gamma}|$ unlabeled entries in range
$A_{\gamma}\times\\{v_{1},...,v_{b_{\gamma}}\\}$ of the labeling table. If no
such $b_{\gamma}$ exists, we let
$b_{\gamma}=\min\\{|A_{\gamma}|,d_{\star}+1\\}$. We further let $B_{\gamma}$,
called the connector of $\gamma$, be an ordered list with elements
$v_{1},...,v_{b_{\gamma}}$. If
$b_{\gamma}=\min\\{|A_{\gamma}|,d_{\star}+1\\}$, we finish processing $\gamma$
with $\hat{E}_{\gamma}=A_{\gamma}\times B_{\gamma}$.

  * (2)

We define $\mathrm{Tag}_{\gamma}$ be an ordered list of pairs $(u,v)$ (called
tags) such that $(u,v)\in A_{\gamma}\times B_{\gamma}$ and the entry $(u,v)$
is unlabeled. $\mathrm{Tag}_{\gamma}$ is in an order which ensures that for
each $(u,v),(u^{\prime},v^{\prime})\in\mathrm{Tag}_{\gamma}$, $(u,v)$ is
ordered before $(u^{\prime},v^{\prime})$ if
$\mathrm{Id}(u)<\mathrm{Id}(u^{\prime})$. For each
$(u,v)\in\mathrm{Tag}_{\gamma}$ at rank $k$, we label the entry $(u,v)$ of the
labeling table with a pair $(\gamma,k)$.

######  Proposition 6.11.

For each $\gamma$ that arrives at step (2),
$|\mathrm{Tag}_{\gamma}|=\Theta(|A_{\gamma}|)$.

###### Proof.

First, by the choice of $b_{\gamma}$, the number of unlabeled pairs in
$A_{\gamma}\times(B_{\gamma}\setminus v_{b_{\gamma}})$ is less than $|{\cal
S}_{\gamma}|=O(|A_{\gamma}|)$, so the number of unlabeled pairs in
$A_{\gamma}\times B_{\gamma}$, i.e. $|\mathrm{Tag}_{\gamma}|$ is at most
$|{\cal S}_{\gamma}|+|A_{\gamma}|=O(|A_{\gamma}|)$. Combining the number of
unlabeled pairs in $A_{\gamma}\times B_{\gamma}$ is at least $|{\cal
S}_{\gamma}|=\Omega(|A_{\gamma}|)$, we conclude
$|\mathrm{Tag}_{\gamma}|=\Theta(|A_{\gamma}|)$. ∎

  * (3)

For each segment $S\in{\cal S}_{\gamma}$ with rank $k$, we assign it the
$k$-ranked $(u,v)$ in $\mathrm{Tag}_{\gamma}$ and set $f(S)=u$ (we also view
$f(S)$ as a singleton set $\\{u\\}$). At last, we set
$\hat{E}_{\gamma}=A_{\gamma}\times B_{\gamma}+\sum_{S\in{\cal
S}_{\gamma}}S\times f(S)$. For each $S\in{\cal S}_{\gamma}$, we call $f(S)$
its witness and we call $f$ the witness function.

For convenience, if a component $\gamma$ has
$\hat{E}_{\gamma}=A_{\gamma}\times B_{\gamma}$, we augment $\hat{E}_{\gamma}$
to $A_{\gamma}\times B_{\gamma}+\sum_{S\in{\cal S}_{\gamma}}S\times f(S)$,
where $f(S)=u$ for all $S\in{\cal S_{\gamma}}$ where $u\in A_{\gamma}$ is an
arbitrary fixed vertex. Therefore, we can write $\hat{E}$ as

$\hat{E}=\sum_{\gamma\in{\cal C}}\hat{E}_{\gamma}=\sum_{\gamma\in{\cal
C}}\left(A_{\gamma}\times B_{\gamma}+\sum_{S\in{\cal S}_{\gamma}}S\times
f(S)\right).$

The structural property of $\hat{E}_{\gamma}$ shown in Proposition 6.12 is
useful in the update algorithm.

######  Proposition 6.12.

For each $\gamma\in{\cal C}$, $\mathrm{Id}(f(S))$ is monotonically increasing
with respect to $S\in{\cal S}_{\gamma}$, namely for each $S,S^{\prime}\in{\cal
S}_{\gamma}$ such that $S$ is ordered before $S^{\prime}$,
$\mathrm{Id}(f(S))\leq\mathrm{Id}(f(S^{\prime}))$. In particular, this
property holds for all ${\cal S}_{\gamma,j}$ since each ${\cal S}_{\gamma,j}$
is a consecutive sublist of ${\cal S}_{\gamma}$.

We store some navigation structures supporting efficient navigation around
artificial edges. These structures include the labeling table, the witness
function $f$ and for each $\gamma$, the segmentation hierarchy ${\cal
S}_{\gamma}$, the adjacency list $A_{\gamma}$ and the connector $B_{\gamma}$.
Besides, we store the following witness lists $C_{\gamma}$ and $C_{\gamma,j}$
for each $\gamma$ and each level $j$. For each $\gamma$, we let
$C_{\gamma}=\\{f(S)\mid S\in{\cal S}_{\gamma}\\}$ (without multiplicity) be an
ordered list collecting all witnesses in ${\cal S}_{\gamma}$, ordered by
$\mathrm{ET}_{\mathrm{glo}}$. Analogously we define an ordered list
$C_{\gamma,j}=\\{f(S)\mid S\in{\cal S}_{\gamma,j}\\}$ for each level $j$ but
$C_{\gamma,j}$ is weighted. Concretely, for each vertex $u\in C_{\gamma,j}$,
we let $u$ have $C_{\gamma,j}$-weight $|f^{-1}(u,{\cal S}_{\gamma,j})|$, where
$f^{-1}(u,{\cal S}_{\gamma,j})$ is the union of segments $S\in{\cal
S}_{\gamma,j}$ such that $f(S)=u$. We proprocess the prefix sum for each
$C_{\gamma,j}$ so that the total $C_{\gamma,j}$-weights of a given range can
be answered in $O(1)$ time. We note that each $C_{\gamma,j}$ is a consecutive
sublist of $C_{\gamma}$ by Proposition 6.12.

######  Lemma 6.13.

The above construction algorithm for $\hat{E}$ takes $O(d_{\star}pm\log n)$
time and extra $O(pm)$ space to store the navigation structures. The size of
$\hat{E}$ is $O(d_{\star}pm\log n)$ and the number of distinct ordered pairs
in $\hat{E}$ is $O(pm\log n)$.

###### Proof.

First we show that the construction algorithm takes $O(d_{\star}pm\log n)$
time. For each component $\gamma$, we need to scan the region
$A_{\gamma}\times B_{\gamma}$ of the labeling table, where $|A_{\gamma}\times
B_{\gamma}|=O(d_{\star}|A_{\gamma}|)$. Summing over all $\gamma$, step (1)
takes totally $O(d_{\star}pm\log n)$ time by Proposition 6.8 where the $O(\log
n)$ factor is from accessing the binary search tree of the table. Step (2) and
(3) takes $O(|A_{\gamma}|)$ time for each $\gamma$, so the total time is
$O(pm)$ summing over all $\gamma$.

Regarding the space taken by the navigation structures, the labeling table
takes space linear to the number of labeled pairs, which is exactly
$\sum_{\gamma}|\mathrm{Tag}_{\gamma}|=\sum_{\gamma}O(|A_{\gamma}|)=O(pm)$.
Other navigation structures take totally $O(pm)$ space following the fact that
for each $\gamma$, $|B_{\gamma}|\leq|A_{\gamma}|$ and both
$\sum_{j}|C_{\gamma,j}|$ and $|C_{\gamma}|$ are at most $|{\cal
S}_{\gamma}|=O(|A_{\gamma}|)$. Therefore, the extra space is $O(pm)$.

We show that the number of distinct pairs in $\hat{E}$ is $O(pm\log n)$ by
bounding the size of $\bigcup_{\gamma}A_{\gamma}\times B_{\gamma}$ and the
size of $\bigcup_{\gamma,S\in{\cal S}_{\gamma}}S\times f(S)$, not counting
mulplicity. The latter is bounded by $O(pm\log n)$ because
$\sum_{\gamma}\sum_{S\in{\cal S}_{\gamma}}|S\times
f(S)|=\sum_{\gamma}O(|A_{\gamma}|\log n)=O(pm\log n)$ where the first equation
follows that the total size of segments in ${\cal S}_{\gamma}$ is
$O(|A_{\gamma}|\log n)$ for each $\gamma$. It remains to bound the size of
$\bigcup_{\gamma}A_{\gamma}\times B_{\gamma}$. Observe that all such pairs
will be labeled in the labeling table, where the number of labeled pairs is
$O(pm)$ as shown above, so $|\bigcup_{\gamma}A_{\gamma}\times
B_{\gamma}|=O(pm)$. Similarly, the size of $\hat{E}$ counting multiplicity is
$|\hat{E}|=\sum_{\gamma}|A_{\gamma}\times
B_{\gamma}|+\sum_{\gamma}\sum_{S\in{\cal S}_{\gamma}}|S\times
f(S)|=O(d_{\star}pm+pm\log n)=O(d_{\star}pm\log n)$.

∎

We have finished the description of affiliated structures and we conclude the
construction time and space in the lemma below.

######  Lemma 6.14.

Given an $n$-vertex $m$-edge graph $G$ with the low degree hierarchy, there is
a deterministic algorithm construct the affiliated structures in time
$O(d_{\star}pm\log^{2}n)$. Furthermore, the affiliated structures take space
$O(pm\log^{2}n)$.

###### Proof.

The 2D range counting structure in Section 6.3 needs $O(d_{\star}pm\log^{2}n)$
construction time and $O(pm\log^{2}n)$ space by Lemma 6.5, because the size of
$E=E(G)+\hat{E}$ is $O(d_{\star}pm\log n)$ and there are only $O(pm\log n)$
distinct pairs in $E$ by Lemma 6.13. The construction of artificial edges
takes $O(d_{\star}pm\log n)$ time and extra space $O(pm)$ by Lemma 6.13.

∎

Construction of $D$-repairing Edges. In what follows, we will show the
algorithm for computing $D$-repairing edges $\hat{F}_{\gamma}$ for each
$\gamma\in{\cal C}$ given any $D$ with $|D|=d\leq d_{\star}$, which is a
subroutine invoked by the update algorithm. We begin by defining unreliable
components and only these components will have a nonempty $\hat{F}_{\gamma}$.
First, each component $\gamma$ with
$|B_{\gamma}|=\min\\{|A_{\gamma}|,d_{\star}+1\\}$ is reliable because
$\hat{E}_{\gamma}$ has been fault-tolerant. For each remaining component
$\gamma$, we say a segment $S\in{\cal S}_{\gamma}$ is an unreliable segment if
its tag $(u,v)$ has both $u,v\in D$, and we say $\gamma$ is unreliable if
there is at least an unreliable segment in ${\cal S}_{\gamma}$.

  * (1)

We can find all unreliable components with the unreliable segments by scanning
the region $D\times D$ of the labeling table. Concretely, for a label
$(\gamma,k)$ of some entry $(u,v)\in D\times D$, if $k\leq|{\cal
S}_{\gamma}|$, the $k$-ranked segment in ${\cal S}_{\gamma}$ is an unreliable
segment of $\gamma$ and $\gamma$ is unreliable.

  * (2)

For each unreliable component $\gamma$, we find a vertex $v_{\gamma}\in
A_{\gamma}\setminus D$ as follows. First we scan the list
$\mathrm{Tag}_{\gamma}$ until we find a tag $(u,v)$ with $u\notin D$ or
$v\notin D$, which means we obtain $v_{\gamma}$ since all $(u,v)$ in
$\mathrm{Tag}_{\gamma}$ are in $A_{\gamma}\times A_{\gamma}$. If we fail to
find a $v_{\gamma}$ by scanning $\mathrm{Tag}_{\gamma}$, we directly scan the
list $A_{\gamma}$ to get $v_{\gamma}$. If we still cannot find $v_{\gamma}$,
it means $A_{\gamma}\subseteq D$.

  * (3)

For each unreliable component $\gamma$ with a $v_{\gamma}\in
A_{\gamma}\setminus D$ found in step (2), we do the following for each of its
unreliable segments $S$ to generate $\hat{F}_{\gamma}$ (initially
$\hat{F}_{\gamma}$ is empty). If $S$ is a singleton set (i.e. $S\in{\cal
S}_{1}$) containing a vertex $v$, we add an edge $(v_{\gamma},v)$ to
$\hat{F}_{\gamma}$. Otherwise, $S$ has at most two child-segments $S_{1}$ and
$S_{2}$ in the segmentation hierarchy. Let $(u_{1},v_{1})$ and $(u_{2},v_{2})$
be tags of $S_{1}$ and $S_{2}$. For each of $u_{1},v_{1},u_{2},v_{2}$, add an
edge connecting it with $v_{\gamma}$ to $\hat{F}_{\gamma}$.

######  Lemma 6.15.

Given a set $D$ where $|D|=d\leq d_{\star}$, there is a deterministic
algorithm computing a set of $D$-repairing edges $\hat{F}_{\gamma}$ for each
$\gamma\in{\cal C}$, such that vertices in $A_{\gamma}\setminus D$ are
connected by edges $\hat{E}_{\gamma}\cup\hat{F}_{\gamma}$ (or possibly
$A_{\gamma}\subseteq D$). The size of $\hat{F}=\bigcup_{\gamma\in{\cal
C}}\hat{F}_{\gamma}$ is $O(d^{2})$ and the running time of this algorithm is
$O(d^{2}\log n)$.

###### Proof.

First we show that for each reliable component $\gamma$, $\hat{E}_{\gamma}$
can connect all vertices in $A_{\gamma}\setminus D$. By the definition, a
reliable $\gamma$ will either have
$|B_{\gamma}|=\min\\{|A_{\gamma}|,d_{\star}+1\\}$ or all segments in ${\cal
S}_{\gamma}$ are reliable. In the former case, we have either
$A_{\gamma}\subseteq D$ or some $v\in B_{\gamma}\setminus D\subseteq
A_{\gamma}\setminus D$ connects all vertices in $A_{\gamma}$, so vertices in
$A_{\gamma}\setminus D$ are connected to $v$ by $\hat{E}_{\gamma}$. In the
latter case, consider the root segment $S=A_{\gamma}$ of ${\cal S}_{\gamma}$.
The tag $(u,v)$ of $S$ has either $u=f(S),u\notin D$ or $v\in
B_{\gamma},v\notin D$. Because $A_{\gamma}\times\\{u\\}=S\times
f(S)\subseteq\hat{E}_{\gamma}$ and $A_{\gamma}\times\\{v\\}\subseteq
A_{\gamma}\times B_{\gamma}\subseteq\hat{E}_{\gamma}$, vertices in
$A_{\gamma}\setminus D$ are connected by $\hat{E}_{\gamma}$.

For each unreliable component $\gamma$, we will show that vertices in
$A_{\gamma}\setminus D$ are connected by
$\hat{E}_{\gamma}\cup\hat{F}_{\gamma}$. Assume that the root segment
$S=A_{\gamma}$ is unreliable, otherwise vertices in $A_{\gamma}\setminus D$
are connected by $\hat{E_{\gamma}}$ by the same argument. Also assume that in
step (2) we found the vertex $v_{\gamma}\in A_{\gamma}\setminus D$, otherwise
we have $A_{\gamma}\subseteq D$. We claim that each $v\in A_{\gamma}\setminus
D$ is connected to $v_{\gamma}$ by $\hat{E}_{\gamma}\cup\hat{F}_{\gamma}$. For
each $v\in A_{\gamma}\setminus D$, let $S=\\{v\\}$ be the singleton segment of
$v$ in ${\cal S}_{\gamma}$. If $S$ is unreliable, then an edge
$(v_{\gamma},v)$ added to $\hat{F}_{\gamma}$ in step (3) will connect $v$ to
$v_{\gamma}$. Otherwise, $S$ is reliable and because the root segment is
unreliable, there is a reliable segment $S^{\prime}$ (an ancestor of $S$ in
${\cal S}_{\gamma}$) such that $v\in S^{\prime}$ and the parent segment of
$S^{\prime}$ is unreliable. Let $(u^{\prime},v^{\prime})$ be the tag of
$S^{\prime}$. In step (3), we have either $u^{\prime}\notin
D,(u^{\prime},v_{\gamma})\in\hat{F}_{\gamma}$ or $v^{\prime}\notin
D,(v^{\prime},v_{\gamma})\in\hat{F}_{\gamma}$. Combining the fact that $v\in
S^{\prime}$ and
$S^{\prime}\times\\{u^{\prime},v^{\prime}\\}\subseteq(S^{\prime}\times
f(S^{\prime}))\cup(A_{\gamma}\times B_{\gamma})\subseteq\hat{E}_{\gamma}$, we
have $v$ and $v_{\gamma}$ are connected by
$\hat{E}_{\gamma}\cup\hat{F}_{\gamma}$.

The bound $|\hat{F}|=O(d^{2})$ is obtained as follows. From the algorithm, the
number of $D$-repairing edges we added is linear to the number of unreliable
segments, which is equal to the number of labeled entries in region $D\times
D$ of the labeling table, which is at most $O(d^{2})$.

The running time of this algorithm is $O(d^{2}\log n)$. Observe that in step
(1) we take $O(d^{2}\log n)$ time to scan the region $D\times D$ of the
labeling table (the $\log n$ factor is from the underlying binary search tree
of the table) and step (3) takes time linear to the number of unreliable
segments, which is $O(d^{2})$. To bound the running time of step (2), we use
the fact that tags in all $\mathrm{Tag}_{\gamma}$ are distinct and charge the
running time on tags in $D\times D$ and unreliable components. Concretely, if
we found $v_{\gamma}$ when scanning $\mathrm{Tag}_{\gamma}$, the running time
is linear to one plus the number of tags in $\mathrm{Tag}_{\gamma}\cap(D\times
D)$ we scanned. Then we charge $O(1)$ costs on the unreliable $\gamma$ and
each such tag. If $v_{\gamma}$ is found by taking $O(|A_{\gamma}|)$ time to
directly scan the whole $A_{\gamma}$, we charge $O(1)$ costs on each tag in
$\mathrm{Tag}_{\gamma}\cap(D\times D)$, since
$|\mathrm{Tag}_{\gamma}\cap(D\times
D)|=|\mathrm{Tag}_{\gamma}|=\Theta(|A_{\gamma}|)$ by Proposition 6.11.
Therefore, the total running time of step (2) is proportional to the number of
unreliable components plus the number of label pairs in $D\times D$, which is
$O(d^{2})$.

∎

##  7 Update and Query Algorithms

In this section, we will show the update and query algorithms. The update
algorithm is introduced in Section 7.1 and Section 7.2, and we describe the
query algorithm in Section 7.3. We conclude the main result of $d$-vertex-
failure connectivity oracles in Theorem 7.1..

######  Theorem 7.1.

Given a $n$-vertex $m$-edge undirected graph $G$ with an upper bound
$d_{\star}$ of the size of failure sets, there exists deterministic
$d_{\star}$-vertex-failure connectivity oracles that use either

  * •

$O(m\cdot\beta(n))$ space, $\hat{O}(m)+\tilde{O}(md_{\star})$ preprocessing
time, $\hat{O}(d^{2})$ update time and $O(d)$ query time, where $\beta(n)$ can
be any slowly growing function e.g. $\beta(n)=\log^{*}n$, or

  * •

$O(m\log^{3}n)$ space171717The space can be improved to $O(m\log^{2}n)$ as
discussed in Footnote 16 at a cost of increasing the update time by an
$O(\log^{1+\epsilon}n)$ factor for any $\epsilon>0$., $O(mn\log n)$
preprocessing time, $\bar{O}(d^{2}\log^{3}n\log^{4}d)$ update time and $O(d)$
query time.

All the $m$ factors can be replaced by $\bar{m}=\min\\{m,n(d_{\star}+1)\\}$ by
the standard sparsification algorithm in [NI92], at a cost of $O(m)$
additional preprocessing time.

The update time is from Theorem 7.2. The query time is from Section 7.3. The
preprocessing time is from Theorem 5.3 (or Theorem 5.4) on the low degree
hierarchy and Lemma 6.14 on the affiliated structures. See Footnote 16 and
Remark 6.10 for some improvements on the space.

###  7.1 The Update Algorithm

Given a failure set $D$ with $|D|=d\leq d_{\star}$, the update algorithm will
compute the connectivity of second-type objects in the abstract graph $H$. Let
$\hat{{\cal T}}$ denote all second-type objects. Let ${\cal C}_{D}$ denotes
the set of affected components and we have $|{\cal C}_{D}|=O(pd)$ since there
are at most $d$ affected components each level.

######  Theorem 7.2.

Let $G$ be a graph with a $(p,\Delta)$-low degree hierarchy and affiliated
structures prepared. Given a set of $D$ failed vertices with $|D|=d\leq
d_{\star}$, there is a deterministic algorithm that computes a partition
$\hat{\cal R}$ of $\hat{{\cal T}}$ such that for each
$\hat{\tau},\hat{\tau}^{\prime}\in\hat{{\cal T}}$, they are connected in $H$
if and only if they are in the same group of $\hat{{\cal R}}$. The running
time of this algorithm is $O(\Delta^{2}p^{2}d^{2}\log n+\Delta
p^{2}d^{2}\log^{4}(\Delta pd)\log n)$.

Instead of constructing the abstract graph $H$ and working directly on $H$,
our algorithm will actually consider some disjoint intervals on
$\mathrm{ET}_{\mathrm{glo}}$, obtained by “linearlizing” the affected
subtrees. Strictly speaking, for each affected tree, we apply Lemma 6.3 on it
with failed vertices $D\cap V(\tau)$, and get a set of disjoint intervals on
$\mathrm{ET}(\tau)$, each of which is owned by an affected subtree. Recall
that $U(\tau)$ is a consecutive sublist of $\mathrm{ET}_{\mathrm{glo}}$. By
taking the restrictions of these intervals on $U(\tau)$,we can obtain some
disjoint intervals on $\mathrm{ET}_{\mathrm{glo}}$. After processing all
affected trees, let ${\cal I}$ denote the whole set of intervals on
$\mathrm{ET}_{\mathrm{glo}}$ we obatined.

######  Proposition 7.3.

The number of intervals is $|{\cal I}|=O(\Delta pd)$ and the time to construct
${\cal I}$ is $O(\Delta pd\log n)$. For each affected subtrees
$\hat{\tau}\in\hat{\cal\tau}$, the union of intervals it owns is exactly its
non-failed terminals $U(\hat{\tau})\setminus D$.

###### Proof.

Recall that in ${\cal T}$, the Steiner trees in the same level are disjoint.
Thus there are at most $O(pd)$ failed vertices appearing on all trees in
${\cal T}$. The trees with failed vertices can be easily identified in $O(pd)$
time since the low degree hierarchy is stored explicitly. Then this
proposition directly follows Lemma 6.3. ∎

Our algorithm will connect intervals in ${\cal I}$ using a multiset $E_{D}$ of
ordered pairs (equivalent to undirected edges) defined by

$E_{D}=E-\bar{E}_{D}=E-\sum_{\gamma\in{\cal
C}_{D}}\hat{E}_{\gamma}=E-\sum_{\gamma\in{\cal C}_{D}}\left(A_{\gamma}\times
B_{\gamma}+\sum_{S\in{\cal S}_{\gamma}}S\times f(S)\right),$

where $E$ are edges we stored in the 2D range counting structure and
$\bar{E}_{D}=\sum_{\gamma\in{\cal C}_{D}}\hat{E}_{\gamma}$ represents
“invalid” artificial edges of affected components. Observe that two intervals
$I_{1},I_{2}\in{\cal I}$ are connected by an edge in $E_{D}$ whenever there is
an ordered pair in $E_{D}$ with one entry in $I_{1}$ and the other one in
$I_{2}$, namely $|E_{D}\cap(I_{1}\times I_{2})|+|E_{D}\cap(I_{2}\times
I_{1})|>0$. We say $I_{1}$ and $I_{2}$ are adjacent in this case.

######  Lemma 7.4.

With access to the low-degree hierarchy and affiliated structures, there is a
deterministic algorithm that computes a partition ${\cal R}$ of ${\cal I}$
such that for any $I,I^{\prime}\in{\cal I}$, they are connected by a path only
with edges in $E_{D}$ if and only if they are in the same group of ${\cal R}$.
The running time of this algorithm is $O(|{\cal I}|^{2}\log n+|{\cal
I}|\cdot|{\cal C}_{D}|\log^{4}|{\cal I}|\log n)$.

In Section 7.2, we will show the algorithm in Lemma 7.4, which computes the
connectivity of intervals over $E_{D}$, but before that, we complete our
update algorithm using Lemma 7.4 as a subroutine.

The last step of our update algorithm is to compute the desired partition
$\hat{\cal R}$ of affected subtrees by further merging groups of intervals
through the connectivity from affected subtrees and $D$-repairing edges. Let
${\cal R}$ be the partition of ${\cal I}$ computed by Lemma 7.4. Let
$\hat{F}_{D}=\sum_{\gamma\in{\cal C}\setminus{\cal C}_{D}}\hat{F}_{\gamma}$ by
collecting $D$-repairing edges of unaffected components. Then we use edges in
$\hat{F}_{D}$ to merge groups in ${\cal R}$. Concretely, for each
$(u,v)\in\hat{F}_{D}$, if $u$ and $v$ belong to some $I_{u},I_{v}\in{\cal I}$
respectively, we merge the groups containing $I_{u}$ and $I_{v}$ into a new
group of ${\cal R}$. Lastly, for each affected subtree $\hat{\tau}$, we merge
the groups with at least one interval owned by $\hat{\tau}$ into a new group.
The partition $\hat{\cal R}$ of $\hat{\cal T}$ is constructed by, for each
group $R\in{\cal R}$, putting the owners of intervals in $R$ into a group
$\hat{R}\in\hat{\cal R}$.

Now we show the correctness of the update algorithm assuming Lemma 7.4.

###### Proof of Theorem 7.2.

For each second-type object $\hat{\tau}\in\hat{\cal T}$, let $\hat{\cal
R}(\hat{\tau})$ denote the group containing $\hat{\tau}$, and let ${\cal
I}(\hat{\tau})$ denote intervals owned by $\hat{\tau}$.

First, we will show that if two second-type object
$\hat{\tau},\hat{\tau}^{\prime}\in\hat{\cal T}$ are connected in $H$, then
$\hat{\cal R}(\hat{\tau})$ and $\hat{\cal R}(\hat{\tau}^{\prime})$ are the
same. Let $P$ be a simple path connecting $\hat{\tau}$ and
$\hat{\tau}^{\prime}$ in $H$. Let $\hat{\tau}_{1}$ and $\hat{\tau}_{2}$ be any
two second-type objects on $P$ such that there is no other second-type object
between them on $P$. We will show that $\hat{\tau}_{1}$ and $\hat{\tau}_{2}$
belong to the same group of $\hat{\cal R}$, so $\hat{\tau}$ and
$\hat{\tau}^{\prime}$ are in the same group. To show the claim, there are two
cases.

Case 1.$\hat{\tau}_{1}$ and $\hat{\tau}_{2}$ are adjacent via an edge on $P$.
From the definition of $H$ (Definition 6.1), this edge corresponds to an
original edge in $E(G)$ which connects one vertex $v_{1}\in U(\hat{\tau}_{1})$
and another vertex $v_{2}\in U(\hat{\tau}_{2})$. Therefore, $v_{1}$ and
$v_{2}$ belong to some $I_{1}\in{\cal I}(\hat{\tau_{1}})$ and $I_{2}\in{\cal
I}(\hat{\tau_{2}})$ respectively, which implies $I_{1}$ and $I_{2}$ are in the