######  Definition 3.11 (Cut-witness).

A _cut-witness_ is an assignment of lengths $\ell^{\prime}(e)\geq 0$ to every
edge $e\in E(G)$, such that, if we denote by $A^{\prime}$ and $B^{\prime}$ the
current sets $A_{1}$ and $B_{1}$ of vertices respectively, and by $E^{*}$ the
set of all special edges with both endpoints in $B^{\prime}$, then:

  * •

$\sum_{e\in E(G)}\ell^{\prime}(e)\leq\frac{\Delta}{2\eta\log^{4}n}+\sum_{e\in
E(G)\setminus E^{*}}\ell(e)$; and

  * •

the distance in graph $G$, with respect to edge lengths
$\ell^{\prime}(\cdot)$, from $A^{\prime}$ to $B^{\prime}$ is at least
$\frac{1}{64}$.

Next, we define the notion of an _acceptable path_ in $G$, and we will require
that the oracle, in every iteration, either returns an acceptable path, or
returns a cut-witness.

######  Definition 3.12 (Acceptable Path).

A path $P$ in the current graph $G$ is called _acceptable_ if $P$ is a simple
path, connecting a vertex of $A_{1}$ to a vertex of $B_{1}$, the length of $P$
with respect to the current edge lengths $\ell(\cdot)$ is at most $1$, and no
inner vertices of $P$ belong to $B_{1}$.

We are now ready to define the oracle.

######  Definition 3.13 (The Oracle).

An oracle for the MWU framework is an algorithm that, in every iteration,
either returns an acceptable path $P$, or returns a cut-witness, or returns
“FAIL”. The probability that the oracle ever returns “FAIL” must be bounded by
$1/2$.

#### The MWU-Based Algorithm.

We describe the modified MWU-based algorithm, denoted by ALG-MWU in Figure 2;
the description excludes the implementation of the oracle, that will be
discussed later.

Alg-MWU • Let $A_{1}\subseteq A$ and $B_{1}\subseteq B$ be the sets of
vertices that do not serve as endpoints of any path in the set
${\mathcal{Q}}_{0}$ constructed in the preprocessing step. • Initialize the
data structures: – Set ${\mathcal{Q}}=\emptyset$; – For every edge $e\in
E(G)$, if $e$ is a regular edge, set $\ell(e)=0$, otherwise set
$\ell(e)=\frac{1}{\Lambda}$. – For every special edge $e$, set $n(e)=0$. •
Perform at most $\Delta-|{\mathcal{Q}}_{0}|$ iterations, where in each
iteration we apply the oracle. – If the oracle returned “FAIL”, then return
“FAIL” and terminate the algorithm; – If the oracle returned a cut-witness,
return the cut-witness and terminate the algorithm; – Otherwise, the oracle
must have returned an acceptable path $P$ connecting a vertex $a\in A_{1}$ to
a vertex $b\in B_{1}$. * remove $a$ from $A_{1}$ and $b$ from $B_{1}$; * add
$P$ to ${\mathcal{Q}}$; * for each special edge $e\in E(P)$, increase $n(e)$
by $1$, and, if $n(e)$ reaches $\eta$, double $\ell(e)$ and set $n(e)=0$.

Figure 2: Alg-MWU

Before we discuss the implementation of the oracle, and an efficient
implementation of Algorithm ALG-MWU, we first show that we can use the
algorithm in order to solve the $r$-restricted $\mathsf{RouteAndCut}$ problem.
Observe first that, if the total running time of the oracle, over the course
of all iterations, is bounded by $T$, then the total running time of Algorithm
ALG-MWU is bounded by $O(|T|)+O(|E(G)|)\leq O(|T|)+O(n\cdot(n-|B|))$.
Moreover, since the probability that the oracle ever returns “FAIL” is at most
$1/2$, the probability that algorithm ALG-MWU terminates with a “FAIL” is
bounded by $1/2$.

Let ${\mathcal{Q}}$ be the set of paths obtained when Algorithm ALG-MWU
terminates, and let
${\mathcal{Q}}^{\prime}={\mathcal{Q}}\cup{\mathcal{Q}}_{0}$ be the final set
of paths that we obtain. Clearly, every path in ${\mathcal{Q}}^{\prime}$
connects a vertex of $A$ to a vertex of $B$. We start by showing that the
paths in ${\mathcal{Q}}^{\prime}$ cause congestion at most $4\eta\log n$, and
that the endpoints of all paths in ${\mathcal{Q}}^{\prime}$ are disjoint, in
the following simple observation.

######  Observation 3.14.

The endpoints of the paths in ${\mathcal{Q}}^{\prime}$ are disjoint, and the
congestion caused by the paths in ${\mathcal{Q}}^{\prime}$ in $G$ is bounded
by $4\eta\log n$.

###### Proof.

It is easy to verify that the endpoints of all paths in
${\mathcal{Q}}^{\prime}$ are disjoint. First, the preprocessing step, in every
iteration selects a regular edge $e=(a,b)$ with $a\in A$ and $b\in B$, adds
the path $Q=(e)$ to $Q_{1}$, and then deletes $a$ from $A$ and $b$ from $B$.
This ensures that vertices $a$ and $b$ cannot serve as endpoints of any paths
that are subsequently added to ${\mathcal{Q}}_{0}$, or to ${\mathcal{Q}}$.
Additionally, whenever Algorithm ALG-MWU adds a new path $P$ connecting a
vertex $a^{\prime}\in A_{1}$ to a vertex $b^{\prime}\in B_{1}$ to
${\mathcal{Q}}$, we delete $a^{\prime}$ from $A_{1}$ and $b^{\prime}$ from
$B_{1}$. Therefore, $a^{\prime}$ and $b^{\prime}$ may not serve as endpoints
of paths that are added subsequently to ${\mathcal{Q}}$. Hence the endpoints
of all paths in ${\mathcal{Q}}^{\prime}$ are disjoint.

Next, we show that every special edge of $G$ belongs to at most $2\eta\log n$
paths of ${\mathcal{Q}}$. At the beginning of the algorithm, we set
$\ell(e)=\frac{1}{\Lambda}=\frac{\Delta}{(n-|B_{1}|)\cdot\eta\cdot\log^{5}n}\geq\frac{\Delta}{n\cdot\eta\cdot\log^{5}n}$.
Let $i_{1},i_{2},\ldots,i_{q}$ denote the indices of the iterations when
$\ell(e)$ was doubled. Notice that, once $\ell(e)$ grows above $1$, it may no
longer be used by any paths that are added to ${\mathcal{P}}$, so
$q\leq\left\lceil\log\Lambda\right\rceil+1\leq 2\log n$ must hold. Moreover,
for all $1\leq j<q$, the number of paths that were added to ${\mathcal{Q}}$
after iteration $i_{j}$ but until iteration $i_{j+1}$ (inclusive), that
contained $e$, is bounded by $\eta$. Similarly, at most $\eta$ paths
containing $e$ were added to ${\mathcal{Q}}$ until iteration $i_{1}$
(inclusive). Altogether, $e$ may belong to at most $2\eta\log n$ paths of
${\mathcal{Q}}$. Since paths of ${\mathcal{Q}}_{0}$ do not contain special
edges, every special edge belongs to at most $2\eta\log n$ paths in
${\mathcal{Q}}^{\prime}$.

Consider now some regular edge $e=(u,v)\in E(G)$. Recall that no regular edge
in $G$ may connect a vertex of $A_{1}$ to a vertex of $B_{1}$. Therefore, if a
path $P\in{\mathcal{Q}}$ contains $e$, then it must contain either the unique
special edge that is incident to $u$ (if it exists), or the unique special
edge that is incident to $v$ (if it exists). Moreover, if a path $Q=(e)$
belongs to ${\mathcal{Q}}_{0}$, then every path $Q^{\prime}\in{\mathcal{Q}}$
that contains $e$ must contain both the unique special edge incident to $u$
and the unique special edge incident to $v$ (since $u\not\in A_{1}$ and
$v\not\in B_{1}$ must hold). Therefore, every regular edge $e$ belongs to at
most $4\eta\log n$ paths in ${\mathcal{Q}}^{\prime}$.

Let $A^{\prime}$ and $B^{\prime}$ denote the sets $A_{1}$ and $B_{1}$,
respectively, at the end of Algorithm ALG-MWU. Notice that $A^{\prime}$ is a
set of all vertices $a\in A$ that do not serve as endpoints of the paths in
${\mathcal{Q}}^{\prime}$, and similarly, $B^{\prime}$ contains all vertices
$b\in B$ that do not serve as endpoints of the paths in
${\mathcal{Q}}^{\prime}$. We now show an algorithm, that, given a cut-witness
$\left\\{\ell^{\prime}(e)\right\\}_{e\in E(G)}$, computes a cut $(X,Y)$ in $G$
with
$|E_{G}(X,Y)|\leq\frac{64\Delta}{\eta\log^{4}n}+\frac{256|{\mathcal{Q}}|}{\eta}$,
such that $A^{\prime}\subseteq X$ and $B^{\prime}\subseteq Y$ hold.

######  Claim 3.15.

There is a deterministic algorithm, that, given a cut-witness
$\left\\{\ell^{\prime}(e)\right\\}_{e\in E(G)}$ for $G$, obtained at the end
of Algorithm ALG-MWU, computes a cut $(X,Y)$ in $G$ with
$|E_{G}(X,Y)|\leq\frac{64\Delta}{\eta\log^{4}n}+\frac{256|{\mathcal{Q}}^{\prime}|}{\eta}$,
such that $A^{\prime}\subseteq X$ and $B^{\prime}\subseteq Y$ hold. The
running time of the algorithm is $O(|E(G)|)\leq O(n\cdot(n-|B|))$.

###### Proof.

Consider the cut-witness $\left\\{\ell^{\prime}(e)\right\\}_{e\in E(G)}$. We
start by bounding $\sum_{e\in E(G)}\ell^{\prime}(e)$ in the following simple
observation.

######  Observation 3.16.

$\sum_{e\in
E(G)}\ell^{\prime}(e)\leq\frac{\Delta}{\eta\log^{4}n}+\frac{2|{\mathcal{Q}}^{\prime}|}{\eta}$.

###### Proof.

For every special edge $e\in E(G)$, let $\ell^{0}(e)$ denote the length of $e$
at the beginning of Algorithm ALG-MWU, and let $\ell^{*}(e)$ denote the length
of $e$ at the end of the algorithm. We denote by $E^{\prime}$ the set of all
special edges $e\in E(G)$, such that, at the beginning of Algorithm ALG-MWU,
both endpoints of $E^{\prime}$ lied in $B_{1}$, but $e\not\in E^{*}$. For
every edge $e\in E^{\prime}$, at least one endpoint of $e$ was deleted from
$B_{1}$ over the course of the algorithm, and $e$ is the only special edge
incident to that endpoint, so $|E^{\prime}|\leq\Delta$ must hold. Recall that,
at the beginning of the algorithm, every special edge was assigned the length
$\frac{1}{\Lambda}$. Let $E^{\mathsf{spec}}$ denote the set of all special
edges in $G$. For each edge $e\in E^{\mathsf{spec}}$, if $e\not\in
E^{\prime}\cup E^{*}$, then, at the beginning of Algorithm ALG-MWU, $e$ was
incident to some vertex $x\in V(G)\setminus B_{1}$, and moreover, $e$ is the
only special edge incident to $x$. Therefore, $|E(G)\setminus(E^{\prime}\cup
E^{*})|\leq n-|B_{1}|$, and $|E(G)\setminus E^{*}|\leq n-B_{1}+\Delta\leq
2(n-|B_{1}|)$, since $\Delta\leq|A|\leq n-|B_{1}|$. Overall, we get that:

$\sum_{e\in E(G)\setminus
E^{*}}\ell^{0}(e)\leq\frac{2(n-|B_{1}|)}{\Lambda}\leq\frac{2\Delta}{\eta\cdot\log^{5}n},$

since $\Lambda=(n-|B_{1}|)\cdot\frac{\eta\log^{5}n}{\Delta}$.

Let $\hat{E}$ denote the subset of special edge $e\in
E^{\mathsf{spec}}\setminus E^{*}$ with $\ell^{*}(e)>\ell^{0}(e)$. Clearly,
$\sum_{e\in E(G)\setminus E^{*}}\ell^{*}(e)\leq\sum_{e\in E(G)\setminus
E^{*}}\ell^{0}(e)+\sum_{e\in\hat{E}}\ell^{*}(e)$.

Let $q$ be the total number of iterations Algorithm ALG-MWU, so
$|{\mathcal{Q}}|=q$ holds, and denote
${\mathcal{Q}}=\left\\{P_{1},\ldots,P_{q}\right\\}$, where the paths are
indexed in the order in which they were added to ${\mathcal{Q}}$. For all
$1\leq i\leq q$, let $C_{i}$ denote the length of path $P_{i}$ when it was
added to ${\mathcal{Q}}$. Clearly, $C_{i}\leq 1$, and $\sum_{i=1}^{q}C_{i}\leq
q$.

Consider now some edge $e\in\hat{E}$, and recall that $\ell(e)$ was doubled at
least once during the algorithm. Let $\tau$ be the last time when the length
of $e$ was doubled. Then, prior to time $\tau$, there were at least $\eta$
iterations $i$, during which the path $P_{i}$ that was added to
${\mathcal{Q}}$ contained $e$, and the length of $e$ during the corresponding
iteration was $\frac{\ell^{*}(e)}{2}$. In other words, edge $e$ contributes at
least $\frac{\ell^{*}(e)\eta}{2}$ to $\sum_{i=1}^{q}C_{i}$. Therefore, we get
that:

$\sum_{e\in\hat{E}}\ell^{*}(e)\leq\frac{2\sum_{i=1}^{q}C_{i}}{\eta}\leq\frac{2q}{\eta}\leq\frac{2|{\mathcal{Q}}|}{\eta}.$

Altogether, we get that:

$\sum_{e\in E(G)\setminus E^{*}}\ell^{*}(e)\leq\sum_{e\in E(G)\setminus
E^{*}}\ell^{0}(e)+\sum_{e\in\hat{E}}\ell^{*}(e)\leq\frac{2\Delta}{\eta\cdot\log^{5}n}+\frac{2|{\mathcal{Q}}|}{\eta}.$

Lastly, from the definition of the cut-witness, we get that:

$\sum_{e\in E(G)}\ell^{\prime}(e)\leq\frac{\Delta}{2\eta\log^{4}n}+\sum_{e\in
E(G)\setminus
E^{*}}\ell(e)\leq\frac{\Delta}{\eta\log^{4}n}+\frac{2|{\mathcal{Q}}|}{\eta}\leq\frac{\Delta}{\eta\log^{4}n}+\frac{2|{\mathcal{Q}}^{\prime}|}{\eta}.$

Consider the graph $G$ with lengths $\ell^{\prime}(e)$ on its edges $e\in
E(G)$. From the definition of a cut-witness, the length of a shortest-path
(with respect to edge-lengths $\ell^{\prime}(\cdot)$) connecting a vertex of
$A^{\prime}$ to a vertex of $B^{\prime}$ in $G^{\prime}$ is at least
$\frac{1}{64}$.

Consider a thought experiment, where we select a threshold
$\rho\in(0,\frac{1}{64})$ uniformly at random, and then let $X$ be the set of
all vertices $v\in V(G)$, such that the distance from $A^{\prime}$ to $v$,
with respect to the length $\ell^{\prime}(\cdot)$ of edges, is at most $\rho$.
Let $Y=V(G)\setminus X$. It is easy to verify that, since the distance from
$A^{\prime}$ to $B^{\prime}$ in $G$ is at least $\frac{1}{64}$,
$A^{\prime}\subseteq X$ and $B^{\prime}\subseteq Y$ must hold. Moreover, the
probability that an edge $e\in E(G)$ lies in $E_{G}(X,Y)$ is bounded by
$64\ell^{\prime}(e)$. Therefore, the expectation of $|E_{G}(X,Y)|$ is bounded
by $64\sum_{e\in
E(G)}\ell^{\prime}(e)\leq\frac{64\Delta}{\eta\log^{4}n}+\frac{128|{\mathcal{Q}}^{\prime}|}{\eta}$.

By performing a standard ball-growing procedure from the set $A^{\prime}$ of
vertices in graph $G$, we can compute, in time $O(|E(G)|)$, a cut $(X,Y)$ in
$G$ with
$|E_{G}(X,Y)|\leq\frac{64\Delta}{\eta\log^{4}n}+\frac{256|{\mathcal{Q}}^{\prime}|}{\eta}$,
such that $A^{\prime}\subseteq X$ and $B^{\prime}\subseteq Y$. The total
running time of the algorithm is bounded by $O(|E(G)|)\leq O(n\cdot(n-|B|))$.

To summarize, we provided an algorithm for the $r$-restricted
$\mathsf{RouteAndCut}$ problem, that assumes the existence of an oracle.

We now discuss an efficient implementation of our algorithm for the
$\mathsf{RouteAndCut}$ problem, given an efficient implementation of the
oracle. Recall that the time required for the preprocessing step, and for
computing the final cut $(X,Y)$ by the algorithm from 3.15, is bounded by
$O(n\cdot(n-|B|))$. If the running time of the oracle is bounded by $T$, then
the running time of Algorithm ALG-MWU is bounded by $O(T+n\cdot(n-B))$.
Therefore, the total running time of the algorithm for the
$\mathsf{RouteAndCut}$ problem is bounded by $O(T+n\cdot(n-|B|))$. We now
focus on implementing the oracle.

#### Implementing the Oracle: Intuition.

Below we define a problem called $r$-restricted $s$-$t$-SP. The problem is
designed to implement the oracle from Definition 3.13. However, for
convenience, we multiply all edge lengths by factor $\Lambda$, and then round
them up to the next integer. We denote the new edge lengths by $\hat{\ell}(e)$
for $e\in E(G)$. Notice that, throughout the algorithm, the length
$\hat{\ell}(e)$ of every edge $e\in E(G)$ is either $0$, or it is an integer
between $1$ and $\left\lceil\Lambda\right\rceil$. We now define the analogues
of an acceptable path and a cut-witness with respect to the new edge lengths,
that we refer to as _modified acceptable path_ and _modified cut-witness_ ,
respectively.

######  Definition 3.17 (Modified Acceptable Path).

A path $P$ in the current graph $G$ is called a _modified acceptable path for
$G$ with respect to $A_{1}$ and $B_{1}$_, if $P$ is a simple path, connecting
a vertex of $A_{1}$ to a vertex of $B_{1}$, the length of $P$ with respect to
the current edge lengths $\hat{\ell}(\cdot)$ is at most $\Lambda$, and no
inner vertices of $P$ belong to $B_{1}$.

######  Definition 3.18 (Modified Cut-witness).

A _modified cut-witness_ for graph $G$ with respect to $A_{1}$ and $B_{1}$ is
an assignment of lengths $\ell^{\prime\prime}(e)\geq 0$ to every edge $e\in
E(G)$, such that if we denote by $A^{\prime},B^{\prime}$ the current sets
$A_{1},B_{1}$ of vertices, and by $E^{*}$ the set of all special edges with
both endpoints in $B^{\prime}$, then:

  * •

$\sum_{e\in
E(G)}\ell^{\prime\prime}(e)\leq\frac{\Lambda\cdot\Delta}{\eta\log^{4}n}+\sum_{e\in
E(G)\setminus E^{*}}\hat{\ell}(e)$; and

  * •

the distance in graph $G$, with respect to edge lengths
$\ell^{\prime\prime}(\cdot)$, from $A^{\prime}$ to $B^{\prime}$ is at least
$\frac{\Lambda}{32}$.

It is immediate to verify that, if
$\left\\{\ell^{\prime\prime}(e)\right\\}_{e\in E(G)}$ is a modified cut-
witness for $G$, then, by setting the length
$\ell^{\prime}(e)=\frac{\ell^{\prime\prime}(e)}{2\Lambda}$ for every edge
$e\in E(G)$, we obtain a valid cut-witness for $G$. Additionally, if $P$ is a
valid modified acceptable path for $G$, then it is also an acceptable path for
$G$.

In order to implement the oracle, it is now enough to design an algorithm
that, in every iteration, either produces a modified acceptable path in $G$,
or produces a modified cut-witness for $G$, or returns “FAIL”, such that the
probability that the algorithm ever returns “FAIL” is bounded by $1/2$. Recall
that $n-|B_{1}|\leq 2(n-|B|)$ from Inequality 1, and so, from the definition
of $r$-restricted $\mathsf{RouteAndCut}$ problem,
$\frac{(n-|B_{1}|)\cdot\eta}{\Delta}\leq\frac{2(n-|B|)\cdot\eta}{\Delta}\leq
2\cdot 2^{r\cdot\sqrt{\log N}}$ holds.

We now provide a formal definition of the $r$-restricted $s$-$t$-SP problem,
that is designed specifically to provide such an algorithm. For convenience,
in the definition of the problem, we will denote the sets $A_{1},B_{1}$ of
vertices by $A$ and $B$, respectively, and we will denote the edge lengths
$\hat{\ell}(e)$ by $\ell(e)$.

####  3.5.2 The $r$-Restricted $s$-$t$-SP Problem

The input to the $r$-Restricted $s$-$t$-SP problem is a well-structured
$n$-vertex graph $G=(L,R,E)$, parameters $N\geq n$, $\Delta\geq 1$, and
$1\leq\eta\leq\Delta$, and two disjoint subsets $A,B$ of vertices of $G$, such
that no regular edge of $G$ connects a vertex of $A$ to a vertex of $B$ in
$G$, $\Delta\leq n-|B|$, and $\frac{(n-|B|)\cdot\eta}{\Delta}\leq 2\cdot
2^{r\cdot\sqrt{\log N}}$ holds. We also require that $|E|\leq
O(n\cdot(n-|B|))$ and that $1\leq r\leq\left\lceil\sqrt{\log N}\right\rceil$.

Initially, every edge $e\in E(G)$ is assigned a length $\ell(e)$ as follows:
if $e$ is a regular edge then $\ell(e)=0$, and otherwise $\ell(e)=1$. We use a
parameter $\Lambda=\frac{(n-|B|)\eta\cdot\log^{5}n}{\Delta}$, and we
initialize ${\mathcal{Q}}=\emptyset$. While the set $B$ of vertices may change
over the course of the algorithm, parameter $\Lambda$ remains unchanged.

The execution of the algorithm for the $r$-restricted $s$-$t$-SP problem
consists of at most $\Delta$ iterations. In every iteration $i$, the algorithm
must do one of the following:

  * •

either return FAIL;

  * •

or return a modified cut-witness for $G$ with respect to $A$ and $B$ (see
Definition 3.18);

  * •

or return a modified acceptable path $P$ for $G$ with respect to $A$ and $B$
(see Definition 3.17).

In the former two cases, the algorithm terminates. In the last case, let $a\in
A$, $b\in B$ denote the endpoints of path $P$. We remove $a$ from $A$ and $b$
from $B$ and add $P$ to ${\mathcal{Q}}$. Additionally, the lengths of some of
the special edges on $P$ will be doubled; we assume that the algorithm
receives a list of all such edges.

For every special edge $e\in E(G)$, the length of $e$ is doubled once $e$
participates in exactly $\eta$ paths that the algorithm returned, since the
last time the length of $e$ was doubled, or since the beginning of the
algorithm – whatever happened last.

Lastly, we require that the probability that the algorithm ever returns “FAIL”
is bounded by $\frac{1}{2}$. This concludes the definition of the
$r$-restricted $s$-$t$-SP problem.

When an algorithm for the problem computes a modified acceptable path $P$, we
may say, for convenience, that it responds to a short-path query. We note that
the running time of an algorithm for the $s$-$t$-SP problem includes both the
time required to maintain its data structures (total update time), and time
required to compute and output the modified acceptable paths in every
iteration (sometimes referred to as query time).

The following theorem is immediate from the discussion in Section 3.5.1, the
definition of the $r$-restricted $s$-$t$-SP problem, and Inequality 1.

######  Theorem 3.19.

Suppose there is an algorithm for the $r$-restricted $s$-$t$-SP problem, that,
given an input $(G,A,B,\Delta,\eta,N)$ with $|V(G)|=n$, has running time at
most $n\cdot(n-|B|)\cdot T(n,\Delta,\eta,N)$. Then there is an algorithm for
the $r$-restricted $\mathsf{RouteAndCut}$ problem, that, on input
$(G,A,B,\Delta,\eta,N)$ with $|V(G)|=n$, has running time at most
$O\left(n\cdot(n-|B|)\cdot T(n,\Delta,\eta,N)\right)+O(n\cdot(n-|B|))$.

Lastly, we show a simple but not very efficient algorithm for $s$-$t$-SP,
that, combined with Theorem 3.19, will be used as the induction base in the
proof of Theorem 3.9.

####  3.5.3 A Simple Algorithm for $s$-$t$-SP

In this subsection we provide the following simple algorithm for the
$r$-restricted $s$-$t$-SP problem.

######  Theorem 3.20.

For all $r\geq 1$, there is a deterministic algorithm for the $r$-restricted
$s$-$t$-SP problem, that, on input $(G,A,B,\Delta,\eta,N)$ with $|V(G)|=n$,
has running time:
$O\left(n\cdot(n-|B|)\cdot\frac{(n-|B|)\cdot\eta}{\Delta}\cdot\log^{6}N\right)$.

###### Proof.

We define a dynamic graph $H$, and we will eventually apply the algorithm for
maintaining the ES-Tree data structure from Theorem 2.6 to graph $H$, with the
distance parameter $d=\Lambda$.

We initialize graph $H$ as follows. We let
$V(H)=V(G)\cup\left\\{s,t\right\\}$. For every regular edge $e=(u,v)\in E(G)$,
we include edge $e$ with length $\tilde{\ell}(e)=1$ in $H$. For every special
edge $e^{\prime}=(u^{\prime},v^{\prime})\in E(G)$, we include
$\left\lceil\log\Lambda\right\rceil+1$ parallel edges
$e_{1},\ldots,e_{\left\lceil\log\Lambda\right\rceil+1}$, where for all $1\leq
i\leq\left\lceil\log\Lambda\right\rceil+1$, the length
$\tilde{\ell}(e_{i})=2^{i-1}$. Lastly, for every vertex $a\in A$, we add an
edge $(s,a)$ of length $1$, and for every vertex $b\in B$, we add an edge
$(b,t)$ of length $1$ to $H$. Note that graph $H$ can be initialized in time
$O(|E(G)|\cdot\log n)\leq O(n\cdot(n-|B|)\cdot\log n)$. We then initialize the
algorithm for maintaining the ES-Tree data structure from Theorem 2.6 on graph
$H$, with the distance threshold $d=\Lambda$.

Our algorithm consists of at most $\Delta$ iterations. In every iteration, we
check whether $\mbox{\sf dist}_{H}(s,t)\leq\Lambda$ holds, in time $O(1)$,
using the ES-Tree data structure. Assume first that this is the case. Then we
use the ES-Tree data structure to compute the shortest $s$-$t$ path $P$ in the
current graph $H$, of length at most $\Lambda$. From our construction, for
every vertex $b\in B$, there is an edge $(b,t)$ of length $1$ in $H$. This
ensures that path $P$ may not contain vertices of $B$ as inner vertices. Let
$P^{\prime}$ be the path obtained from $P$ by deleting its first and last
vertex. It is then easy to verify that $P^{\prime}$ is a modified acceptable
path, that we return as an output of the current iteration. Let $a\in A$,
$b\in B$ be the endpoints of path $P^{\prime}$. Recall that following the
current iteration, $a$ is deleted from $A$ and $b$ is deleted from $B$.
Additionally, the lengths of some special edges of $E(P^{\prime})$ may be
doubled. We modify graph $H$, in order to reflect these changes as follows. We
delete the edges $(s,a)$ and $(b,t)$ from $H$. Additionally, for every special
edge $e^{\prime}\in E(P)$ whose length was doubled in $G$, we delete the
shortest-length copy of $e^{\prime}$ from $H$.

Assume now that, at the beginning of some iteration, we discover that
$\mbox{\sf dist}_{H}(s,t)>\Lambda$ holds. Then, in the current graph $H$, the
length of the shortest path connecting a vertex of $A$ to a vertex of $B$ is
at least $\Lambda-2\geq\frac{\Lambda}{2}$. We now define the lengths
$\ell^{\prime}(e)$ of edges $e\in E(G)$ as follows. If $e$ is a regular edge
that lies in $H$, then we set $\ell^{\prime}(e)=0$. If $e=(x,y)$ is a special
edge, then we let $\ell^{\prime}(e)$ be the length of the shortest parallel
edge $(x,y)$ in $H$.

Let $A^{\prime}$ and $B^{\prime}$ denote the sets $A$ and $B$ of vertices at
the end of the algorithm, respectively. Clearly, $\sum_{e\in
E(G)}\ell^{\prime}(e)\leq\sum_{e\in E(G)}\ell(e)$ holds. Next, we claim that,
for every path $P$ connecting a vertex $a\in A^{\prime}$ to a vertex $b\in
B^{\prime}$ in $G$, the length $\sum_{e\in
E(P)}\ell^{\prime}(e)\geq\frac{\Lambda}{32}$. Indeed, recall that we have
established that the length of such a path $P$ in graph $H$ is at least
$\frac{\Lambda}{2}$. The only difference between the edge lengths
$\left\\{\tilde{\ell}(e)\right\\}_{e\in E(P)}$ and
$\left\\{\ell^{\prime}(e)\right\\}_{e\in E(P)}$ is that the length
$\tilde{\ell}(e)$ of every regular edge $e\in E(H)$ is $1$, and
$\ell^{\prime}(e)=0$. However, since no regular edge may connect a vertex of
$A$ to a vertex of $B$ in $G$, regular and special edges must alternate on
path $P$, and, since the length of every special edge in $H$ is at least $1$,
the total length $\tilde{\ell}(e)$ of all special edges $e\in E(P)$ is at
least $\frac{\sum_{e^{\prime}\in
E(P)}\hat{\ell}(e^{\prime})}{4}\geq\frac{\Lambda}{32}$.

Let $E^{*}$ be the set of all special edges with both endpoints in
$B^{\prime}$. In order to turn the current assignment
$\left\\{\ell^{\prime}(e)\right\\}_{e\in E(G)}$ of edge lengths to a valid
modified cut-witness, we set the length $\ell^{\prime}(e)$ of every edge $e\in
E^{*}$ to $0$. It is easy to verify that, for every path $P$ connecting a
vertex of $A$ to a vertex of $B$ in $G$, its length remains at least
$\frac{\Lambda}{32}$, and $\sum_{e\in E(G)}\ell^{\prime}(e)\leq\sum_{e\in
E(G)\setminus E^{*}}\ell(e)$ now holds. Therefore, we obtain a valid modified
cut-witness for $G$.

It now remains to analyze the running time of the algorithm. We start by
analyzing the _total update time_ – the time required to maintain all data
structures, which excludes the _query time_ – the time required to compute the
modified acceptable paths in every iteration.

Let $m$ denote the total number of edges that are ever present in $H$, and
recall that $m\leq O(n\cdot(n-|B|)\cdot\log N)$. Once graph $H$ is
initialized, the additional update of the algorithm is bounded by
$O(m\cdot\Lambda)$. Therefore, the total update time that is required in order
to maintain the data structures (excluding the time required to return the
paths in every iteration) is bounded by:

$O(n\cdot(n-|B|)\cdot\Lambda\cdot\log N)\leq
O\left(n\cdot(n-|B|)\cdot\frac{(n-|B|)\cdot\eta}{\Delta}\cdot\log^{6}N\right).$

Assume now that the number of iterations in which the algorithm returned a
modified acceptable path is $q$, and let $P_{1},\ldots,P_{q}$ denote the paths
that the algorithm returned. Then the time that the algorithm spent on
returning these paths is bounded by $\sum_{i=1}^{q}O(|E(P_{i})|)$. Recall that
no regular edge connects a vertex of $A$ to a vertex of $B$ in $G$, and so
regular and special edges alternate on each such path $P_{i}$. Therefore, for
all $1\leq i\leq q$, $|E(P_{i})|$ is asymptotically bounded by the number of
special edges on $P_{i}$.

Consider now some special edge $e$ of $G$. When $e$ is first added to $G$, we
include at most $O(\log n)$ copies of $e$ in $H$. Every time edge $e$
participates in $\eta$ of the paths that the algorithm returns, one of the
copies of $e$ is deleted from $H$. Therefore, copies of a special edge $e$ of
$G$ may participate in at most $O(\eta\log n)$ paths that the algorithm
returns, and, overall, $\sum_{i=1}^{q}|E(P_{i})|\leq O(n\eta\log n)$ (since
there are at most $n$ special edges in $G$). We conclude that the total
running time of the algorithm is bounded by:

$O\left(n\cdot(n-|B|)\cdot\frac{(n-|B|)\cdot\eta}{\Delta}\cdot\log^{6}N\right)+O(n\eta\log
N)\leq
O\left(n\cdot(n-|B|)\cdot\frac{(n-|B|)\cdot\eta}{\Delta}\cdot\log^{6}N\right),$

since $\eta\leq\Delta\leq n-|B|$ from the problem definition.

By combining Theorem 3.20 with Theorem 3.19, and recalling that, in the
$r$-restricted $\mathsf{RouteAndCut}$ problem,
$\frac{(n-|B|)\cdot\eta}{\Delta}\leq 2\cdot 2^{r\cdot\sqrt{\log N}}$ holds, we
obtain the following immediate corollary.

######  Corollary 3.21.

There is a deterministic algorithm for the $r$-restricted
$\mathsf{RouteAndCut}$ problem, that, on input $(G,A,B,\Delta,\eta,N)$ with
$|V(G)|=n$, has running time at most $O\left(n\cdot(n-|B|)\cdot
2^{r\cdot\sqrt{\log N}}\cdot\log^{6}N\right)$.

We will use this corollary in our inductive proof of Theorem 3.9, for the base
case when $r=1$, and also for general values of $r$, when the value of the
parameter $N$ is sufficiently small.

##  4 Tools for Expander-Like Graphs and the $\mathsf{MaintainCluster}$
Problem

In this section we introduce some tools for expander-like graphs, and define
the second main problem that serves as a subroutine in our algorithm for
Maximum Bipartite Matching– the $\mathsf{MaintainCluster}$ problem. We start
by definining subdivided graphs, and providing a new definition of cut
sparsity, that extends the standard definition to graphs with edge lengths in
a natural way.

###  4.1 A Subdivided Graph and a New Definition of Cut Sparsity

We first recall a standard definition of cut sparsity in directed graphs. Let
$G$ be an arbitrary directed graph, and assume that the graph is unweighted,
so all edge lengths and capacities are unit. Under the standard definition,
the sparsity of the cut $(A,B)$ in $G$ is defined as
$\frac{|E_{G}(A,B)|}{\min\left\\{|A|,|B|\right\\}}$.

Suppose now that we are given a well-structured graph $G=(L,R,E)$, with a
proper uniform assignment of lengths to its edges, so the lengths of all
special edges in $G$ are unit. In this case, for a well-structured cut $(A,B)$
in $G$, it would be natural to define its sparsity as
$\frac{|E_{G}(A,B)|}{\min\left\\{|A|,|B|\right\\}}$, to be consistent with the
standard definition of sparsity.

Assume now that we are given a well-structured graph $G=(L,R,E)$, with a
proper assignment of lengths to its edges, but now the lengths of the special
edges may no longer be unit. Several of the expander-based tools that we
define below work best when the underlying graph is unweighted; in the context
of well-structured graphs, this corresponds to having a proper uniform
assignment of edge lengths. A natural way to handle graphs with arbitrary
lengths of special edges in this setting is to suitably _subdivide_ its edges,
so that the lengths of the special edges become unit, but the lengths of all
paths are preserved. We now define a subdivided graph of a well-structured
graph, a notion that we will use later, that will also motivate our modified
definition of cut sparsity.

######  Definition 4.1 (Subdivided Graph).

Let $G=(L,R,E)$ be a perfect well-structured graph with a proper assignment of
lengths $\ell(e)$ to its edges $e\in E$, and let
$G^{\prime}=(L^{\prime},R^{\prime},E^{\prime})$ be another graph. We say that
$G^{\prime}$ is the _subdivided graph of $G$_, and denote $G^{\prime}=G^{+}$,
if $G^{\prime}$ can be obtained from $G$ via the following process. We start
with $G^{\prime}=G$, $L^{\prime}=L,R^{\prime}=R$ and $E^{\prime}=E$, and then
consider every special edge $e\in E$ one by one. Let $e=(u,v)$ be any such
edge, and denote its length $\ell(e)$ by $q$. We replace edge $e$ with a path
$P(e)=(u=x_{1},y_{1},x_{2},y_{2},\ldots,x_{q},y_{q}=v)$. Note that $u\in
R^{\prime}$ and $v\in L^{\prime}$ must hold. We add vertices
$x_{2},\ldots,x_{q}$ to $R^{\prime}$, and vertices $y_{1},\ldots,y_{q-1}$ to
$L^{\prime}$. Edges $(x_{1},y_{1}),\ldots,(x_{q},y_{q})$ become special edges,
and edges $(y_{1},x_{2}),\ldots,(y_{q-1},x_{q})$ become regular edges of
$G^{\prime}$. The lengths of the resulting special edges are set to $1$, while
the lengths of the resulting regular edges are set to $0$, so the length of
the path $P(e)$ is $q=\ell(e)$.

Note that, if $G$ is a perfect well-structured graph with proper edge lengths,
then its subdivided graph $G^{+}$ is a perfect well-structured graph with
proper uniform edge lengths. Therefore, we can use the definition of cut
sparsity for well-structured graphs with proper uniform edge lengths from
above in graph $G^{+}$. Every cut $(A^{\prime},B^{\prime})$ in graph $G^{+}$
naturally also defines a cut $(A,B)$ in $G$, where we set $A=V(G)\cap
A^{\prime}$ and $B=V(G)\cap B^{\prime}$. We will define the sparsity of cuts
in perfect well-structured graphs with proper edge lengths in a natural way,
so that, if a well-structured cut $(A^{\prime},B^{\prime})$ in $G^{+}$ is
$\varphi$-sparse according to the standard definition, then the sparsity of
the corresponding cut $(A,B)$ in $G$ is at most $O(\varphi)$. Notice that,
since graph $G^{+}$ is obtained from $G$ by subdividing some of its edges,
every edge of $G$ may contribute a number of vertices to $A^{\prime}$ and/or
to $B^{\prime}$. We will assign a _weight_ to every vertex of $G$ in order to
reflect this contribution. We use the following definition of vertex weights
throughout the paper.

######  Definition 4.2 (Vertex Weights).

Let $G=(L,R,E)$ be a perfect well-structured graph with a proper assignment of
lengths to its edges. For every vertex $v\in L\cup R$, the _weight_ $w(v)$ is
defined to be the length of the unique special edge that is incident to $v$.
For a subset $S$ of vertices of $G$, we define $w(S)=\sum_{v\in S}w(v)$, and
for a subgraph $G^{\prime}$ of $G$ we define $w(G^{\prime})=w(V(G^{\prime}))$.

We are now ready to define the sparsity of cuts in perfect well-structured
graphs.

######  Definition 4.3 (Cut Sparsity).

Let $G=(L,R,E)$ be a perfect well-structured graph with a proper assignment of
lengths on its edges, and let $(A,B)$ be a well-structured cut in $G$. The
_sparsity_ of cut $(A,B)$ is:

$\Phi_{G}(A,B)=\frac{|E_{G}(A,B)|}{\min\left\\{w(A),w(B)\right\\}}.$

We will use the following simple observation whose proof can be found in
Section A.1 of the Appendix.

######  Observation 4.4.

Let $G=(L,R,E)$ be a perfect well-structured graph with proper lengths
$\ell(e)$ on its edges $e\in E$, and let $G^{+}$ be its subdivided graph.
Assume further that we are given a parameter $0<\varphi<1$, and that the
length of every edge in $G$ is at most $\frac{1}{4\varphi}$. Let
$(A^{\prime},B^{\prime})$ be a well-structured cut in $G^{+}$ of sparsity at
most $\varphi$, and let $(A,B)$ be the corresponding cut in $G$, where
$A=A^{\prime}\cap V(G)$ and $B=B^{\prime}\cap V(G)$. Then $(A,B)$ is a well-
structured cut in $G$, $w(A)\geq|A^{\prime}|/8$, $w(B)\geq|B^{\prime}|/8$, and
$\Phi_{G}(A,B)\leq 8\varphi$.

The next observation allows us to transform a weakly well-structured cut into
a strongly well-structured cut in a perfect well-structured graph, while
roughly preserving its sparsity. The proof appears in Section A.2 of the
Appendix.

######  Observation 4.5.

Let $G=(L,R,E)$ be a perfect well-structured graph with a proper assignment of
lengths $\ell(e)$ to its edges $e\in E$, and let $0<\varphi\leq 1$ be a
parameter. Let $W=\sum_{e\in E}\ell(e)$, and assume that, for all $e\in E$,
$\ell(e)\leq\frac{W}{2}$. Let $(A,B)$ be a $\frac{\varphi}{2}$-sparse weakly
well-structured cut in $G$. Then there is a $\varphi$-sparse strongly well-
structured cut $(A^{\prime},B^{\prime})$ in $G$ with $w(A^{\prime})\geq
w(A)/4$ and $w(B^{\prime})\geq w(B)/4$. Moreover, there is a deterministic
algorithm, that, given $G$, $\varphi$, and cut $(A,B)$ in $G$, computes cut
$(A^{\prime},B^{\prime})$ in $G$ with the above properties in time
$O(\min\left\\{\operatorname{Vol}_{G}(A),\operatorname{Vol}_{G}(B)\right\\})$.

###  4.2 The $\mathsf{MaintainCluster}$ Problem

We abstract the central technical tool that we use in order to maintain
expander-like graphs by the $\mathsf{MaintainCluster}$ problem, that we define
next.

As an input to the $\mathsf{MaintainCluster}$ problem, we are given a perfect
well-structured graph $G$ with a proper assignment of lengths $\ell(e)$ to its
edges $e\in E(G)$, that subsequently undergoes some updates, though $G$
remains a perfect well-structured graph throughout the algorithm. Recall that
we have defined vertex weights for perfect well-structured graphs, where the
weight of a vertex $v$ is the length of the unique special edge incident to
$v$. For every vertex $v\in V(G)$, we denote by $w^{0}(v)$ its initial weight
in the initial input graph $G$, and we denote $W^{0}(G)=\sum_{v\in
V(G)}w^{0}(v)$. We are now ready to define the $\mathsf{MaintainCluster}$
problem.

######  Definition 4.6.

The input to the $\mathsf{MaintainCluster}$ problem consists of a perfect
well-structured graph $G=(L,R,E)$ with $|V(G)|=n$, together with a proper
assignment of lengths $\ell(e)$ to its edges $e\in E$, and parameters $N\geq
W^{0}(G)$, $1\leq\Delta\leq N$, $1\leq\eta\leq\Delta$, and $d\geq(\log
N)^{64}$, such that $\frac{\Delta\cdot d}{\eta}\leq n$, and $N$ is greater
than a sufficiently large constant, so that, for example, $N>2^{2^{c_{2}}}$
holds, where $c_{2}$ is the constant from Theorem 3.9.

The algorithm consists of at most $\Delta$ iterations. At the beginning of
every iteration $i$, the algorithm is given two vertices $x,y\in V(G)$, and it
must return a simple path $P_{i}$ in $G$ connecting $x$ to $y$ of length at
most $d$. (We may sometimes say that the algorithm is given a short-path query
between the pair $(x,y)$ of vertices, and it returns the path $P_{i}$ in
response to the query). After that the length of some special edges on path
$P_{i}$ may be doubled. We are guaranteed that the following property holds:

  1. P1.

If $\tau^{\prime}>\tau$ are two times at which the length of some edge $e\in
E(G)$ is doubled, then the algorithm returned at least $\eta$ paths in
response to queries during the time interval $(\tau,\tau^{\prime}]$ that
contained $e$.

The algorithm may, at any time, produce a strongly well-structured cut $(X,Y)$
in $G$ of sparsity $\Phi_{G}(X,Y)\leq\frac{(\log N)^{64}}{d}$. If $w(X)\leq
w(Y)$, then let $Z=X$ and $Z^{\prime}=Y$; otherwise, let $Z=Y$ and
$Z^{\prime}=X$. We also let $J^{\prime}\subseteq Z^{\prime}$ denote the set of
vertices that serve as endpoints of the edges of $E_{G}(X,Y)$. The vertices of
$Z\cup J^{\prime}$ are then deleted from $G$, and the algorithm continues with
the resulting graph $G=G[Z^{\prime}\setminus J^{\prime}]$. Note that we are
guaranteed that $G$ remains a perfect well-structured graph after this
modification. Once $|V(G)|\leq n/2$ holds, the algorithm terminates, even if
fewer than $\Delta$ iterations have passed.

The algorithm may also, at any time, return “FAIL”. The probability that the
algorithm ever returns “FAIL” must be bounded by $1/N^{4}$.

For an integer $1\leq r\leq\left\lceil\sqrt{\log N}\right\rceil$, we say that
an instance $(G,\Delta,\eta,d,N)$ of the $\mathsf{MaintainCluster}$ problem is
$r$-restricted, if $d\leq 2^{r\cdot\sqrt{\log N}}$.

We prove the following theorem that provides an algorithm for the
$\mathsf{MaintainCluster}$ problem. Though we do not use the theorem directly,
it easily follows from our results and we believe that it is interesting in
its own right.

######  Theorem 4.7.

There is a randomized algorithm for the $\mathsf{MaintainCluster}$ problem,
that, on an instance $(G,\Delta,\eta,d,N)$ of the problem, has running time at
most $O\left(W^{0}(G)\cdot(W^{0}(G)+\Delta)\cdot 2^{O(\sqrt{\log
N}\cdot\log\log N)}\right)$.

###  4.3 The $\mathsf{MaintainSpecialCluster}$ Problem

We will sometimes need to use a slight variation of the
$\mathsf{MaintainCluster}$ problem, that we refer to as the
$\mathsf{MaintainSpecialCluster}$ problem. In this problem, as before, we are
given a perfect well-structured graph $G$ with proper lengths $\ell(e)$ on its
edges $e\in E(G)$, that subsequently undergoes some updates, though $G$
remains a perfect well-structured graph throughout the algorithm. Graph $G$ is
given in the adjacency-list representation, and initially all special edges
have length $1$. For every vertex $v\in V(G)$, we define its initial weight
$w^{0}(v)$ exactly as before, and we denote $W^{0}(G)=\sum_{v\in
V(G)}w^{0}(v)$ as before. In addition to the perfect well-structured graph
$G$, the algorithm is given as input a subset $\beta$ of vertices of $G$. Over
the course of the algorithm, some vertices may be deleted from the set
$\beta$, but we will ensure that, throughout the algorithm, every special edge
incident to a vertex in $\beta$ has length $1$. For intuition, the vast
majority of the vertices of the input graph $G$ lie in $\beta$, and this
property is preserved throughout the entire algorithm. Unlike the
$\mathsf{MaintainCluster}$ problem, in a short-path query, we are now given a
single vertex $x\in V(G)$, and we need to return a path $P$ in the current
graph $G$ that connects $x$ to any vertex of $\beta$, such that no inner
vertices of $P$ lie in $\beta$. The last endpoint of the path $P$ is then
deleted from $\beta$, and the lengths of some edges of the path $P$ may be
doubled, like in the $\mathsf{MaintainCluster}$ problem. Like in the
$\mathsf{MaintainCluster}$ problem, the algorithm may, at any time, return a
sparse strongly well-structured cut $(X,Y)$ in $G$, but now we require that
$w(X)\geq 1.8w(\beta\cap X)=1.8|\beta\cap X|$, that is, much of the weight of
the vertices in $X$ must come from vertices that do not lie in $\beta$. The
vertices of $X$, and all endpoints of the edges in $E_{G}(X,Y)$ are then
deleted from $G$, and the algorithm continues. We are now ready to define the
$\mathsf{MaintainSpecialCluster}$ problem formally.

######  Definition 4.8.

The input to the $\mathsf{MaintainSpecialCluster}$ problem consists of a
perfect well-structured graph $G=(L,R,E)$ with a proper assignment of lengths
$\ell(e)$ to its edges $e\in E$, that are given in the adjacency-list
representation, such that the length of every special edge is $1$.
Additionally, we are given a subset $\beta\subseteq V(G)$ of vertices with
$|\beta|\geq\frac{99|V(G)|}{100}$, and parameters $N\geq W^{0}(G)$,
$1\leq\Delta\leq\frac{|\beta|}{(\log N)^{128}}$, $1\leq\eta\leq\Delta$, and
$d\geq(\log N)^{64}$, such that $\frac{\Delta\cdot
d}{\eta}\leq|V(G)|-|\beta|+\Delta\cdot(\log N)^{64}$, and $N$ is greater than
a sufficiently large constant. Over the course of the algorithm, vertices may
be deleted from set $\beta$, and the lengths of some special edges may be
increased, but the length of every special edge incident to a vertex that
currently lies in $\beta$ is always $1$.

The algorithm consists of at most $\Delta$ iterations. At the beginning of
every iteration $i$, the algorithm is given a vertex $x\in V(G)$, and it must
return a simple path $P_{i}$ in $G$ connecting $x$ to any vertex $y\in\beta$,
such that the length of the path is at most $d$, and no inner vertices on the
path lie in $\beta$ (if $x\in\beta$, that we require that path $P_{i}$ only
consists of the vertex $x$). After that, the length of some special edges on
path $P_{i}$ may be doubled, and vertex $y$ is deleted from $\beta$. We are
guaranteed that Property P1 from the definition of the
$\mathsf{MaintainCluster}$ problem holds.

The algorithm may, at any time, produce a strongly well-structured cut $(X,Y)$
in $G$ of sparsity $\Phi_{G}(X,Y)\leq\frac{(\log N)^{64}}{d}$, such that
$w(X)\geq 1.8|\beta\cap X|$ holds. Let $J^{\prime}\subseteq Y$ denote the set
of vertices that serve as endpoints of the edges of $E_{G}(X,Y)$. The vertices
of $X\cup J^{\prime}$ are then deleted from $G$, and the algorithm continues
with the resulting graph $G=G[Y\setminus J^{\prime}]$. Note that we are
guaranteed that $G$ remains a perfect well-structured graph after this
modification.

The algorithm may also, at any time, return “FAIL”. The probability that the
algorithm ever returns “FAIL” must be bounded by $1/4$. Lastly, if the number
of vertices in $\beta$ decreases by a factor $2$, the algorithm terminates.

For an integer $1\leq r\leq\left\lceil\sqrt{\log N}\right\rceil$, we say that
an instance $(G,\beta,\Delta,\eta,d,N)$ of the
$\mathsf{MaintainSpecialCluster}$ problem is $r$-restricted, if $d\leq
2^{r\cdot\sqrt{\log N}}$.

We prove the following theorem that provides an algorithm for the
$\mathsf{MaintainSpecialCluster}$ problem.

######  Theorem 4.9.

There is a randomized algorithm for the $\mathsf{MaintainSpecialCluster}$
problem, that, on an instance $(G,\beta,\Delta,\eta,d,N)$ of the problem, has
running time at most:

$O\left(W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{O(\sqrt{\log
N}\cdot\log\log N)}\right).$

In order to prove Theorems 4.7 and 4.9, we use induction. Specifically, we
will consider $r$-restricted instances of both problems problem, from smaller
to larger values of $r$. The following theorem summarizes our main result for
the $r$-restricted $\mathsf{MaintainCluster}$ and
$\mathsf{MaintainSpecialCluster}$ problems. It uses the large enough constants
$c_{1}\gg c_{2}$ that also appear in the statment of Theorem 3.9.

######  Theorem 4.10.

For all $r\geq 1$, there is a randomized algorithm for the $r$-restricted
$\mathsf{MaintainCluster}$ problem, that, on an instance $(G,\Delta,\eta,d,N)$
of the problem, has running time at most:

$c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r}+c_{1}W^{0}(G)\cdot\Delta\cdot\log^{4}N,$

and there is a randomized algorithm for the the $r$-restricted
$\mathsf{MaintainSpecialCluster}$ problem, that, on an instance
$(G,\beta,\Delta,\eta,d,N)$ of the problem, has running time at most:

$c_{1}\cdot W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log
N}}\cdot(\log N)^{16c_{2}r}.$

Note that the proof of Theorem 4.7 easily follows from Theorem 4.10. Indeed,
consider any instance $(G,\Delta,\eta,d,N)$ of the $\mathsf{MaintainCluster}$
problem. From the definition of the problem, $d\leq\frac{n\eta}{\Delta}\leq
n\leq N$ must hold, and so in particular $d\leq 2^{r\cdot\sqrt{\log N}}$, for
$r=\left\lceil\sqrt{\log N}\right\rceil$. Therefore, any instance of the
problem is $r$-restricted for $r=\left\lceil\sqrt{\log N}\right\rceil$. By
applying Theorem 4.10 with $r=\left\lceil\sqrt{\log N}\right\rceil$, we obtain
an algorithm for the given instance of the $\mathsf{MaintainCluster}$ problem,
whose running time is bounded by:

$\begin{split}&O\left(W^{0}(G)\cdot(W^{0}(G)+\Delta)\cdot 2^{O(\sqrt{\log
N})}\cdot(\log N)^{O(\sqrt{\log N})}\right)\\\ &\quad\quad\quad\quad\leq
O\left(W^{0}(G)\cdot(W^{0}(G)+\Delta)\cdot 2^{O(\sqrt{\log N}\cdot\log\log
N)}\right),\end{split}$

as required.

Similarly, the proof of Theorem 4.9 easily follows from Theorem 4.10. Indeed,
consider any instance $(G,\beta,\Delta,\eta,d,N)$ of the
$\mathsf{MaintainSpecialCluster}$ problem, and denote $n=|V(G)|$. As before,
from the definition of the problem, $d\leq\frac{n\eta}{\Delta}\leq n\leq N$
must hold, and so in particular $d\leq 2^{r\cdot\sqrt{\log N}}$, for
$r=\left\lceil\sqrt{\log N}\right\rceil$. Therefore, any instance of the
problem is $r$-restricted for $r=\left\lceil\sqrt{\log N}\right\rceil$. By
applying Theorem 4.10 with $r=\left\lceil\sqrt{\log N}\right\rceil$, we obtain
an algorithm for the given instance of the $\mathsf{MaintainSpecialCluster}$
problem, whose running time is bounded by:

$\begin{split}O\left(W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot
2^{O(\sqrt{\log N})}\cdot(\log N)^{O(\sqrt{\log N})}\right)&\\\
\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\leq
O\left(W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{O(\sqrt{\log
N}\cdot\log\log N)}\right).\end{split}$

It now remains to complete the proofs of Theorems 3.9 and 4.10.

###  4.4 Completing the Proofs of Theorem 3.9 and Theorem 4.10

We prove the two theorems together, by induction on $r$. Specifically, we
first show that, given an efficient algorithms for the $r$-restricted
$\mathsf{MaintainCluster}$ and $\mathsf{MaintainSpecialCluster}$ problems, we
can obtain an efficient algorithm for the $(r+1)$-restricted
$\mathsf{RouteAndCut}$ problem. This result is summarized in the following
theorem, whose proof is deferred to Section 5.

######  Theorem 4.11.

Suppose that, for some parameter $r\geq 1$, there exists a randomized
algorithm for the $r$-restricted $\mathsf{MaintainCluster}$ problem, that,
given as input an instance $(G,\Delta,\eta,d,N)$ of the problem, has running
time at most: $c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r}+c_{1}\cdot W^{0}(G)\cdot\Delta\cdot\log^{4}N$. Assume further
that there also exists a randomized algorithm for the $r$-restricted
$\mathsf{MaintainSpecialCluster}$ problem, that, on an instance
$(G,\beta,\Delta,\eta,d,N)$ of the problem, has running time at most:
$c_{1}\cdot W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log
N}}\cdot(\log N)^{16c_{2}r}$. Then there is a randomized algorithm for the
$(r+1)$-restricted $\mathsf{RouteAndCut}$ problem, that, given as input an
instance $(G,A,B,\Delta,\eta,N)$ of the problem with $|V(G)|=n$, has running
time at most $c_{1}\cdot n\cdot(n-|B|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+8c_{2}}$.

Next, we show that an efficient algorithm for the $r$-restricted
$\mathsf{RouteAndCut}$ problem implies an efficient algorithm for the
$r$-restricted $\mathsf{MaintainCluster}$ and
$\mathsf{MaintainSpecialCluster}$ problems, in the following theorem, whose
proof is deferred to Sections 6 and 7.

######  Theorem 4.12.

Suppose that, for some parameter $r\geq 1$, there exists a randomized
algorithm for the $r$-restricted $\mathsf{RouteAndCut}$ problem, that, given
as an input an instance $(G,A,B,\Delta,\eta,N)$ of the problem with
$|V(G)|=n$, has running time at most $c_{1}\cdot n\cdot(n-|B|)\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}(r-1)+8c_{2}}$. Then there exists
a randomized algorithm for the $r$-restricted $\mathsf{MaintainCluster}$
problem, that, on input $(G,\Delta,\eta,d,N)$ has running time at most:
$c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r}+c_{1}\cdot W^{0}(G)\cdot\Delta\cdot\log^{4}N$, and there exists
a randomized algorithm for the $r$-restricted
$\mathsf{MaintainSpecialCluster}$ problem, that, on input
$(G,\beta,\Delta,\eta,d,N)$ has running time at most: $c_{1}\cdot
W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r}$.

The majority of the remainder of this paper is dedicated to the proofs of
Theorem 4.11 and Theorem 4.12. The proofs of Theorem 3.9 and Theorem 4.10
easily follow from these theorems, as we show next.

Recall that, from Corollary 3.21, there is an algorithm for the $1$-restricted
$\mathsf{RouteAndCut}$ problem, that, given as input an instance
$(G,A,B,\Delta,\eta,N)$ of the problem with $|V(G)|=n$, has running time at
most $O\left(n\cdot(n-|B|)\cdot 2^{r\cdot\sqrt{\log
N}}\cdot\log^{6}N\right)\leq c_{1}\cdot n\cdot(n-|B|)\cdot 2^{\sqrt{\log
N}}\cdot(\log N)^{8c_{2}}$, since we can assume that $c_{1}$ is a large enough
constant. This proves the induction base for the $\mathsf{RouteAndCut}$
problem. From Theorem 4.12 we then conclude that there exists a randomized
algorithm for the $1$-restricted $\mathsf{MaintainCluster}$ problem, that, on
input $(G,\Delta,\eta,d,N)$ has running time at most:
$c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}}+c_{1}\cdot W^{0}(G)\cdot\Delta\cdot\log^{4}N$, and that there is
the $1$-restricted $\mathsf{MaintainSpecialCluster}$ problem, that, on input
$(G,\beta,\Delta,\eta,d,N)$ has running time at most: $c_{1}\cdot
W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}}$. This proves the induction base for the
$\mathsf{MaintainCluster}$ and the $\mathsf{MaintainSpecialCluster}$ problems.

For the induction step, consider an integer $r\geq 1$, and assume that both
Theorem 3.9 and Theorem 4.10 hold for $r$-restricted instances. Then from
Theorem 4.11, there is a randomized algorithm for the $(r+1)$-restricted
$\mathsf{RouteAndCut}$ problem, that, given as input an instance
$(G,A,B,\Delta,\eta,N)$ of the problem with $|V(G)|=n$, has running time at
most $c_{1}\cdot n\cdot(n-|B|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+8c_{2}}$, proving Theorem 3.9 for $(r+1)$-restricted instances.
By applying Theorem 4.12 with integer $(r+1)$, we then conclude that there
exists a randomized algorithm for the $(r+1)$-restricted
$\mathsf{MaintainCluster}$ problem, that, on input $(G,\Delta,\eta,d,N)$ has
running time at most: $c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log
N}}\cdot(\log N)^{16c_{2}(r+1)}+c_{1}\cdot W^{0}(G)\cdot\Delta\cdot\log^{4}N$,
and that there exists a randomized algorithm for the $(r+1)$-restricted
$\mathsf{MaintainSpecialCluster}$ problem, that, on input
$(G,\beta,\Delta,\eta,d,N)$ has running time at most: $c_{1}\cdot
W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}(r+1)}$. This proves proving Theorem 4.10 for $(r+1)$-restricted
instances of $\mathsf{MaintainCluster}$ and $\mathsf{MaintainSpecialCluster}$.
This completes the proofs of Theorems 3.9 and 4.10 from Theorems 4.11 and
4.12. In the next three sections we prove Theorem 4.11 and Theorem 4.12.

##  5 From $r$-Restricted $\mathsf{MaintainCluster}$ and
$\mathsf{MaintainSpecialCluster}$ to $(r+1)$-Restricted
$\mathsf{RouteAndCut}$: Proof of Theorem 4.11

The proof of Theorem 4.11 follows from the following theorem:

######  Theorem 5.1.

Suppose that, for some parameter $r\geq 1$, there exists a randomized
algorithm for the $r$-restricted $\mathsf{MaintainCluster}$ problem, that,
given as input an instance $(G,\Delta,\eta,d,N)$ of the problem, has running
time at most: $c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r}+c_{1}\cdot W^{0}\cdot\Delta\cdot\log^{4}N$. Suppose further that
there exists a randomized algorithm for the $r$-restricted
$\mathsf{MaintainSpecialCluster}$ problem, that, given as input an instance
$(G,\beta,\Delta,\eta,d,N)$ of the problem, has running time at most:
$c_{1}\cdot W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log
N}}\cdot(\log N)^{16c_{2}r}$. Then there is a randomized algorithm for the
$(r+1)$-restricted $s$-$t$-SP problem, that, given an instance
$(G,A,B,\Delta,\eta,N)$ of the problem with $|V(G)|=n$, has running running
time at most $c_{1}\cdot n\cdot(n-|B|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+7c_{2}}$.

Before we provide the proof of Theorem 5.1, we show that the proof of Theorem
4.11 follows from it.

Proof of Theorem 4.11: Consider a parameter $r\geq 1$, and assume that there
exists a randomized algorithm for the $r$-restricted
$\mathsf{MaintainCluster}$ problem, that, on input $(G,\Delta,\eta,d,N)$, has
running time at most: $c_{1}\cdot(W^{0}(G))^{2}\cdot 2^{c_{2}\sqrt{\log
N}}\cdot(\log N)^{16c_{2}r}+c_{1}\cdot W^{0}\cdot\Delta\cdot\log^{4}N$. Assume
further that there exists a randomized algorithm for the $r$-restricted
$\mathsf{MaintainSpecialCluster}$ problem, that, on input
$(G,\beta,\Delta,\eta,d,N)$, has running time at most: $c_{1}\cdot
W^{0}(G)\cdot(W^{0}(G)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r}$. From Theorem 5.1, there exists a randomized algorithm for the
$(r+1)$-restricted $s$-$t$-SP problem, that, on input $(G,A,B,\Delta,\eta,N)$
with $|V(G)|=n$, has running running time at most $c_{1}\cdot
n\cdot(n-|B|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}r+7c_{2}}$.
From Theorem 3.19, there exists a randomized algorithm for the
$(r+1)$-restricted $\mathsf{RouteAndCut}$ problem, that, on input
$(G,A,B,\Delta,\eta)$ with $|V(G)|=n$, has running time is at most:

$\begin{split}&O\left(c_{1}\cdot n\cdot(n-|B|)\cdot 2^{c_{2}\sqrt{\log
N}}\cdot(\log N)^{16c_{2}r+7c_{2}}\right)+O(n\cdot(n-|B|))\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\leq c_{1}\cdot
n\cdot(n-|B|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+8c_{2}},\end{split}$

since $c_{2}$ is a sufficiently large constant.

From now on we focus on the proof of Theorem 5.1. We denote the randomized
algorithms for the $r$-restricted $\mathsf{MaintainCluster}$ and
$\mathsf{MaintainSpecialCluster}$ problems from the theorem statement by
${\mathcal{A}}$ and ${\mathcal{A}}^{\prime}$, respectively.

We denote the input to the $(r+1)$-restricted $s$-$t$-SP problem by
$(G,A,B,\Delta,\eta,N)$, where $G=(L,R,E)$ is an $n$-vertex well-structured
graph, $A$ and $B$ are two disjoint subsets of vertices of $G$, and $N\geq n$,
$\Delta\geq 1$, and $1\leq\eta\leq\Delta$ are parameters. Recall that no
regular edge of $G$ connects a vertex of $A$ to a vertex of $B$, $\Delta\leq
n-|B|$, $|E|\leq O(n\cdot(n-|B|))$, and $\frac{(n-|B|)\cdot\eta}{\Delta}\leq
2\cdot 2^{(r+1)\sqrt{\log N}}$ hold.

Recall that, as the algorithm progresses, we maintain lengths $\ell(e)$ for
edges $e\in E(G)$, and, additionally, some vertices may leave the sets $A$ and
$B$. Since the number of iterations is bounded by $\Delta$, at most $\Delta$
vertices may be deleted from $A$ and from $B$. For convenience, we denote by
$A^{0}$ and $B^{0}$ the initial sets $A$ and $B$, respectively, to distinguish
them from the sets that are maintained during the algorithm.

Note that we can assume that $N$ is greater than a sufficiently large
constant, so that, for example, $N>2^{2^{c_{2}}}$ holds. Indeed, if this is
not the case, then, from Theorem 3.20, we obtain a determinisic algorithm that
solves the input instance of $s$-$t$-SP in time:

$\begin{split}O\left(n\cdot(n-|B^{0}|)\cdot\frac{(n-|B^{0}|)\cdot\eta}{\Delta}\cdot\log^{6}N\right)&\leq
O\left(n\cdot(n-|B^{0}|)\cdot N\cdot\log^{6}N\right)\\\ &\leq c_{1}\cdot
n\cdot(n-|B^{0}|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+7c_{2}},\end{split}$

since $n\leq N\ll c_{1}$, and $\eta\leq\Delta$ (recall that, by definition,
$c_{1}\gg c_{2}$ holds). Therefore, we assume from now on that $N$ is
sufficiently large.

Additionally, we can assume that
$\frac{(n-|B^{0}|)\cdot\eta}{\Delta}>2^{4\sqrt{\log N}}$, since otherwise,
from Theorem 3.20, we obtain a determinisic algorithm that solves the input
instance of $s$-$t$-SP in time:

$\begin{split}O\left(n\cdot(n-|B^{0}|)\cdot\frac{(n-|B^{0}|)\cdot\eta}{\Delta}\cdot\log^{6}N\right)&\leq
O\left(n\cdot(n-|B^{0}|)\cdot 2^{4\sqrt{\log N}}\cdot\log^{6}N\right)\\\ &\leq
c_{1}\cdot n\cdot(n-|B^{0}|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+7c_{2}}.\end{split}$

Therefore, we assume from now on that:

$\frac{(n-|B^{0}|)\cdot\eta}{\Delta}>2^{4\sqrt{\log N}}$ (2)

Throughout the algorithm, we use the parameter
$\Lambda=(n-|B^{0}|)\cdot\frac{\eta\cdot\log^{5}n}{\Delta}$. We let $H$ be the
graph that is obtained from $G$, by adding a source vertex $s$, that connects
to every vertex $a\in A$ with a length-$0$ edge, and a destination vertex $t$,
to which every vertex $b\in B$ connects with a length-$0$ edge. If an edge
$e\in E(G)$ is a special edge for graph $G$, then $e$ remains a special edge
for $H$. All other edges of $H$, including edges incident to $s$ and $t$, are
called regular edges. For every edge $e\in E(G)$, its length in $H$ remains
the same as in $G$, so for convenience, we denote the length of every edge
$e\in E(H)$ by $\ell(e)$.

At the beginning of the algorithm, for each edge $e\in E(H)$, its length
$\ell(e)$ is set as follows: if $e$ is a regular edge, then $\ell(e)=0$, and
if $e$ is a special edge, then $\ell(e)=1$. The algorithm proceeds as follows.
We start by setting ${\mathcal{Q}}=\emptyset$, and then perform at most
$\Delta$ iterations. In every iteration, the algorithm must do one of the
following:

  1. R1.

either return FAIL;

  2. R2.

or return a simple $s$-$t$ path $P$ of length at most $\Lambda$ in the current
graph $H$, such that $P$ contains exactly one vertex of $B$ – the penultimate
vertex on the path.

  3. R3.

or compute an assignment $\ell^{\prime}(e)\geq 0$ of lengths to all edges
$e\in E(H)$, such that, if we denote by $\tilde{E}$ the set of all special
edges of $G$ with both endpoints in $B$, then $\sum_{e\in
E(H)}\ell^{\prime}(e)\leq\frac{\Lambda\cdot\Delta}{\eta\log^{4}n}+\sum_{e\in
E(H)\setminus\tilde{E}}\ell(e)$; the length $\ell^{\prime}(e)$ of every edge
$e$ that is incident to $s$ or to $t$ is $0$; and the distance from $s$ to $t$
in $H$, with respect to edge lengths $\ell^{\prime}(\cdot)$, is at least
$\frac{\Lambda}{32}$;

Note that, if the algorithm returns assignments of lengths $\ell^{\prime}(e)$
to edges $e\in E(H)$ as in Outcome R3, then these assignments of edge lengths
define a modified cut-witness for $G$ (see Definition 3.18). In this case, the
algorithm terminates, and returns the lengths $\ell^{\prime}(e)$ of all edges
$e\in E(H\setminus\left\\{s,t\right\\})$. Slightly abusing the notation, for
the sake of simplicity, we will call an assignment of lengths
$\ell^{\prime}(e)$ to the edges $e\in E(H)$ as described in Outcome R3 a _cut-
witness_.

If the algorithm returns an $s$-$t$ path $P$ as in Outcome R2, then
$P\setminus\left\\{s,t\right\\}$ is a modified acceptable path for $G$ (see
Definition 3.17). To simplify the notation, we say that a path $P$ described
in Outcome R2 is an _acceptable path_. If the algorithm returns an acceptable
path $P$, then we let $P^{\prime}=P\setminus\left\\{s,t\right\\}$, and we let
$a\in A$, $b\in B$ be the endpoints of path $P^{\prime}$. We remove $a$ from
$A$ and $b$ from $B$, add $P^{\prime}$ to ${\mathcal{Q}}$, and delete the
edges $(s,a)$ and $(b,t)$ from $H$. Additionally, the lengths of some of the
special edges on $P$ may be doubled; we assume that the algorithm receives the
list of all such edges.

From the problem definition, for every special edge $e\in E(H)$, the length of
$e$ is doubled once $e$ participates in exactly $\eta$ paths that the
algorithm returned since the last time the length of $e$ was doubled, or since
the beginning of the algorithm – whatever happened last.

Lastly, in the case of Outcome R1, we terminate the algorithm and return
“FAIL”, but we require that the probability that the algorithm ever returns
“FAIL” is bounded by $\frac{1}{2}$.

### Some Useful Bounds

We denote by $E^{\mathsf{spec}}$ the set of all special edges in graph $G$,
and we denote by $E^{*}\subseteq E^{\mathsf{spec}}$ the set of all special
edges $e=(u,v)$, such that $u,v\in B$ holds at the end of the algorithm.
Recall that the length of a special edge $e$ may only be increased once it
participates in some path that the algorithm returns, and, if a vertex $x\in
B$ lies on any path that the algorithm returns, then $x$ is deleted from $B$.
Therefore, every edge $e\in E^{*}$ has length $1$ throughout the algorithm. We
start by bounding $|E^{\mathsf{spec}}\setminus E^{*}|$ in the following simple
observation.

######  Observation 5.2.

$|E^{\mathsf{spec}}\setminus E^{*}|\leq 2(n-|B^{0}|)$.

###### Proof.

We partition the set $E^{\mathsf{spec}}\setminus E^{*}$ if edges into two
subsets: set $E_{1}$ contains all edges $e$, such that at least one endpoint
of $e$ lies in $V(G)\setminus B^{0}$, and set $E_{2}$ contains all remaining
edges of $E^{\mathsf{spec}}\setminus E^{*}$. Since every edge of $E_{1}$ is
incident to a vertex of $V(G)\setminus B^{0}$, and every vertex of $G$ may
serve as an endpoint of at most one special edge, $|E_{1}|\leq n-|B^{0}|$ must
hold. Consider now some edge $e\in E_{2}$. From the definition, over the
course of the algorithm, at least one endpoint of $e$ was deleted from $B$.
Since at most $\Delta$ vertices are deleted from $B$ over the course of the
algorithm, and since each such vertex may serve as an endpoint of at most one
special edge, we get that $|E_{2}|\leq\Delta\leq n-|B^{0}|$, from the
definition of the $s$-$t$-SP problem. Altogether, we get that
$|E^{\mathsf{spec}}\setminus E^{*}|\leq|E_{1}|+|E_{2}|\leq 2(n-|B^{0}|)$.

For each edge $e\in E^{\mathsf{spec}}$, let $\ell^{*}(e)$ be the length of $e$
at the end of the algorithm. In the next simple observation we bound
$\sum_{e\in E^{\mathsf{spec}}}\ell^{*}(e)$.

######  Observation 5.3.

$\sum_{e\in
E^{\mathsf{spec}}}\ell^{*}(e)\leq|E^{\mathsf{spec}}|+2(n-|B^{0}|)\log^{5}n$,
and $\sum_{e\in E^{\mathsf{spec}}\setminus E^{*}}\ell^{*}(e)\leq
4(n-|B^{0}|)\log^{5}n$.

###### Proof.

Recall that, at the beginning of the algorithm, for every edge $e\in
E^{\mathsf{spec}}$, we set $\ell(e)=1$. Let $E^{\prime}\subseteq
E^{\mathsf{spec}}$ be the set of all edges $e\in E^{\mathsf{spec}}$ with
$\ell^{*}(e)>1$. Clearly, $\sum_{e\in
E^{\mathsf{spec}}}\ell^{*}(e)\leq|E^{\mathsf{spec}}|+\sum_{e\in
E^{\prime}}\ell^{*}(e)$.

Let $q$ be the total number of iterations of the algorithm, so that, at the
end of the algorithm, $|{\mathcal{Q}}|=q$ holds, and let
${\mathcal{Q}}=\left\\{P_{1},\ldots,P_{q}\right\\}$, where the paths are
indexed in the order in which they were added to ${\mathcal{Q}}$. For all
$1\leq i\leq q$, let $C_{i}$ denote the length of path $P_{i}$ when it was
added to ${\mathcal{Q}}$. Clearly, $C_{i}\leq\Lambda$, and
$\sum_{i=1}^{q}C_{i}\leq q\cdot\Lambda\leq\Delta\cdot\Lambda$.

Consider now some edge $e\in E^{\prime}$, and recall that $\ell(e)$ was
doubled at least once during the algorithm. Let $\tau$ be the last time when
the length of $e$ was doubled. Then, prior to time $\tau$, there were at least
$\eta$ iterations $i$, during which the path $P_{i}$ that was added to
${\mathcal{Q}}$ contained $e$, and the length of $e$ during the corresponding
iteration was $\frac{\ell^{*}(e)}{2}$. In other words, edge $e$ contributes at
least $\frac{\ell^{*}(e)\eta}{2}$ to $\sum_{i=1}^{q}C_{i}$. Altogether, we get
that $\sum_{i=1}^{q}C_{i}\geq\sum_{e\in E^{\prime}}\frac{\ell^{*}(e)\eta}{2}$.
Therefore:

$\sum_{e\in
E^{\prime}}\ell^{*}(e)\leq\frac{2\sum_{i=1}^{q}C_{i}}{\eta}\leq\frac{2\Delta\Lambda}{\eta}\leq
2(n-|B^{0}|)\cdot\log^{5}n,$

since $\Lambda=(n-|B^{0}|)\cdot\frac{\eta\cdot\log^{5}n}{\Delta}$. Altogether,
we get that:

$\sum_{e\in E^{\mathsf{spec}}}\ell^{*}(e)\leq|E^{\mathsf{spec}}|+\sum_{e\in
E^{\prime}}\ell^{*}(e)\leq|E^{\mathsf{spec}}|+2(n-|B^{0}|)\log^{5}n.$

Lastly, from 5.2, $|E^{\mathsf{spec}}|-|E^{*}|\leq 2(n-|B^{0}|)$, and so:

$\sum_{e\in E^{\mathsf{spec}}\setminus E^{*}}\ell^{*}(e)\leq\sum_{e\in
E^{\mathsf{spec}}}\ell^{*}(e)-|E^{*}|\leq|E^{\mathsf{spec}}|+2(n-|B^{0}|)\log^{5}n-|E^{*}|\leq
4(n-|B^{0}|)\log^{5}n.$

Throughout the algorithm, we use a parameter
$N^{\prime}=\max\left\\{N,8n\cdot\log^{5}n\right\\}$. Let $\tau$ be any time
in the algorithm’s execution, and let $H^{\prime}$ be any subgraph of
$H\setminus\left\\{s,t\right\\}$, that is a perfect well-structured graph.
Recall that the weight of every vertex $v\in V(H^{\prime})$ is the length of
the unique special edge incident to $v$. From 5.3, and since
$|E^{\mathsf{spec}}|\leq n$, the total weight of all vertices of $H^{\prime}$
must be bounded by $N^{\prime}$. Notice also that, since $N\geq n$, we get
that $N^{\prime}\leq 8N\log^{5}n\leq N\log^{6}N$. It is then easy to see that:

$\log N^{\prime}\leq\log N+6\log\log
N\leq\left(1+\frac{1}{64c_{2}r}\right)\log N,$ (3)

since $r\leq\left\lceil\sqrt{\log N}\right\rceil$ and $N$ is large enough.
Additionally, $\sqrt{\log N^{\prime}}\leq\sqrt{\log N+6\log\log
N}\leq\sqrt{\log N}+\sqrt{6\log\log N}$. Therefore:

$2^{\sqrt{\log N^{\prime}}}\leq 2^{\sqrt{\log N}}\cdot\log^{6}N\leq
2^{2\sqrt{\log N}}.$ (4)

We will use these facts later.

Algorithm for the $(r+1)$-restricted $s$-$t$-SP problem: The description of
our algorithm for the $(r+1)$-restricted $s$-$t$-SP problem consists of two
parts. In the first part, we provide an algorithm for maintaining an
$\mathcal{ATO}$ for graph $H$. This algorithm in turn exploits algorithm
${\mathcal{A}}$ for the $r$-restricted $\mathsf{MaintainCluster}$ problem and
Algorithm ${\mathcal{A}}^{\prime}$ for the $r$-restricted
$\mathsf{MaintainSpecialCluster}$ problem. In the second part, we use the
algorithm from Theorem 2.7 for the DAG-like SSSP problem on the corresponding
contracted graph.

###  5.1 Part 1 - Maintaining the $\mathcal{ATO}$

In this part we describe our algorithm for maintaining the $\mathcal{ATO}$
$({\mathcal{X}},\rho,U,\gamma)$ for graph $H$. Notice that
$|V(H)|=|V(G)|+2=n+2$. Throughout, we use a parameter
${d=\frac{(n-|B^{0}|)\cdot\eta}{4\Delta\cdot 2^{\sqrt{\log N}}}}$. Notice
that:

$2^{2\sqrt{\log N}}\leq d\leq 2^{r\sqrt{\log N}-1}.$ (5)

Here, the first inequality follows from Inequality 2. The second inequality
follows since the input instance of $s$-$t$-SP is $(r+1)$-restricted, so
$\frac{(n-|B^{0}|)\cdot\eta}{\Delta}\leq 2\cdot 2^{(r+1)\sqrt{\log N}}$ holds.

Let $U\subseteq V(H)\setminus\left\\{s,t\right\\}$ be the collection of all
vertices $v$, such that some special edge of $E^{\mathsf{spec}}$ is incident
to $v$, and let $U^{\prime}=V(H)\setminus U$. Notice that $H[U]$ is a perfect
well-structured graph (see Definition 3.1). We let the initial collection
${\mathcal{X}}$ of vertex subsets contain the set $U$, and, for every vertex
$v\in U^{\prime}$, a set $X_{v}=\left\\{v\right\\}$. For convenience, we
denote $S=\left\\{s\right\\}$ and $T=\left\\{t\right\\}$. We distinguish
between two cases. Case 1 happens when $|U|>2(n-|B^{0}|)\cdot(\log N)^{128}$.
In this case, we let $U$ be the special cluster of the $\mathcal{ATO}$, and we
set $\gamma=|U|-256(n-|B^{0}|)(\log N)^{64}$. Otherwise, Case 2 happens, the
special cluster of the $\mathcal{ATO}$ is undefined, and we set $\gamma=1$.

Next, we assign, to every resulting set $X\in{\mathcal{X}}$, an interval
$I_{X}\subseteq\left\\{1,\ldots,|V(H)|-\gamma+1\right\\}$, so that, for each
regular cluster $X\in{\mathcal{X}}$, $|I_{X}|=|X|$, and, if the special
cluster is defined, then $|I_{U}|=|U|-\gamma+1$. In order to do so, it is
sufficient to define an ordering $\sigma$ of the sets in ${\mathcal{X}}$. We
let $S$ appear first in the ordering, followed by the sets in
$\left\\{X_{v}\mid v\in U^{\prime}\cap L\right\\}$ in an arbitrary order,
followed by set $U$, which is followed by the sets in $\left\\{X_{v}\mid v\in
U^{\prime}\cap R\right\\}$ in an arbitrary order, followed by $T$. Since
vertices of $U^{\prime}$ are not incident to special edges, it is easy to
verify that no edge of $H$ is a right-to-left edge with respect to this
initial $\mathcal{ATO}$. Throughout the algorithm, we refer to each set
$X\in{\mathcal{X}}$ of vertices as a _cluster_. If $|X|=1$, then we say that
$X$ is a _singleton_ cluster. As the algorithm progresses, cluster $U$ may be
partitioned into smaller and smaller clusters, with each such cluster assigned
an interval that is contained in the initial interval $I_{U}$, but the
clusters in $\left\\{X_{v}\mid v\in U^{\prime}\right\\}$, together with their
corresponding intervals $I_{X_{v}}$, remain unchanged. For convenience, we
denote the initial set $U$ by $U^{0}$. We will ensure that, throughout the
algorithm, the following invariants hold:

  1. I1.

If $X\in{\mathcal{X}}$ is a non-singleton cluster, then $H[X]$ is a perfect
well-structured graph;

  2. I2.

If the special cluster is defined, then $U\in{\mathcal{X}}$ holds throughout
the algorithm, and moreover, $|U|\geq\gamma$ always holds; and

  3. I3.

If $e=(x,y)$ is a right-to-left edge with respect to the current
$\mathcal{ATO}$, and $X,Y\in{\mathcal{X}}$ are the clusters that contain $x$
and $y$, respectively, so that $Y$ appears before $X$ in the ordering $\sigma$
of clusters of ${\mathcal{X}}$ defined by the $\mathcal{ATO}$, then $e$ must
be a special edge, and moreover, $X=\left\\{x\right\\}$ and
$Y=\left\\{y\right\\}$ must hold; in other words, $X$ and $Y$ are both
singleton clusters.

It is easy to verify that the invariant holds for the initial $\mathcal{ATO}$.

For each cluster $X$ that is ever added to ${\mathcal{X}}$, we denote by
$X^{0}$ the set $X$ when it was just added to ${\mathcal{X}}$. If $|X^{0}|>1$
(that is, $X$ is not a singleton cluster when it is added to ${\mathcal{X}}$),
then, from Invariant I1, $H[X]$ is a perfect well-structured graph, so weights
of vertices of $X$ are well defined. In such a case, we denote by $W^{0}(X)$
the total weight of all vertices of $X$ when $X$ is added to ${\mathcal{X}}$.
Whenever a non-singleton regular cluster $X$ is added to set ${\mathcal{X}}$,
we define the parameter
${d_{X}=\min\left\\{\frac{|X^{0}|\cdot\eta}{\Delta},d\right\\}}$. We may
sometimes refer to $d_{X}$ as $d_{X^{0}}$. Next, we partition all clusters
that are ever added to ${\mathcal{X}}$ into _leaf_ and _non-leaf_ clusters.

######  Definition 5.4 (Leaf and Non-Leaf Clusters).

Let $X$ be a cluster that was just added to ${\mathcal{X}}$. We say that $X$
is a _leaf cluster_ , if $|X^{0}|\leq\frac{\Delta\cdot(\log N)^{128}}{\eta}$.
If $X$ is not a leaf cluster, then we call it a _non-leaf_ cluster.

Recall that, if $U$ is a special cluster, then $|U^{0}|>2(n-|B^{0}|)\cdot(\log
N)^{128}$. Since $\Delta\leq n-|B^{0}|$ from the definition of the $s$-$t$-SP
problem, we get that a special cluster may not be a leaf cluster.

Recall that in general, once a cluster $X$ is added to the collection
${\mathcal{X}}$ of clusters of an $\mathcal{ATO}$, it must remain in
${\mathcal{X}}$ throughout the algorithm, though we may delete some vertices
from $X$. A new cluster $Y$ may only be added to the set ${\mathcal{X}}$ if it
is a subset of some cluster $X$ that currently lies in ${\mathcal{X}}$. When
we describe our algorithm for maintaining the $\mathcal{ATO}$, it will be
convenient for us to sometimes remove a cluster $X$ from the set
${\mathcal{X}}$, and then immediately reinsert it into ${\mathcal{X}}$. This
is only done for clarity of exposition and convenience of analysis, and we do
not need to do so in order to maintain the $\mathcal{ATO}$. Additionally, we
will sometimes replace a cluster $X\in{\mathcal{X}}$ with a new collection of
clusters, each of which contains a single vertex of $X$. In such a case we
could simply identify $X$ with one of the new clusters and implement this
update to ${\mathcal{X}}$ via a sequence of cluster splitting operations,
though for clarity of exposition we will treat all newly inserted clusters as
new clusters, and we will think of $X$ as being removed from ${\mathcal{X}}$.

Next, we describe an algorithm for maintaining each cluster $X$ that is added
to ${\mathcal{X}}$. We employ different algorithms for leaf clusters, non-leaf
regular clusters, and the special cluster, if it is defined. We now describe
each of the three algorithms in turn.

####  5.1.1 Leaf Clusters

Let $X$ be a leaf cluster that was just added to ${\mathcal{X}}$. If $X$ is a
singleton cluster, then no further processing of this cluster is needed.
Assume now that $X$ is a non-singleton cluster. We immediately remove $X$ from
${\mathcal{X}}$, and instead add, for every vertex $v\in X$, a new singleton
cluster $\left\\{v\right\\}$ to ${\mathcal{X}}$. We assign, to each such new
cluster $\left\\{v\right\\}$, an interval $I_{\left\\{v\right\\}}\subseteq
I_{X}$ of length $1$, so that all intervals corresponding to the vertices of
$X\cap L$ appear before all intervals corresponding to the vertices of $X\cap
R$. Notice that the only new right-to-left edges that are introduced by this
transformation are the edges of $E_{H}(X\cap R,X\cap L)$, which are all
special edges. The number of such edges is $|X\cap R|=|X\cap L|\leq|X|$. We
say that these new right-to-left edges are _bad edges_ , and that they are
_owned_ by the leaf cluster $X$. We denote the set of these edges by
$E^{\mathsf{bad}}(X)$. From the above discussion,
$|E^{\mathsf{bad}}(X)|\leq|X|$, and each edge $e\in E^{\mathsf{bad}}(X)$ has
$\operatorname{span}(e)\leq|X|$.

####  5.1.2 Non-Leaf Regular Clusters

Whenever a new non-leaf regular cluster $X$ is added to ${\mathcal{X}}$, we
initialize Algorithm ${\mathcal{A}}$ for the $r$-restricted
$\mathsf{MaintainCluster}$ problem on graph $H[X^{0}]$, with parameters
$\Delta$ and $\eta$ that remain unchanged, parameter $d$ replaced with
$d_{X}$, and parameter $N$ replaced with $N^{\prime}$. We denote this
instantiation of Algorithm ${\mathcal{A}}$ by ${\mathcal{A}}(X)$. We now
verify that $(H[X^{0}],\Delta,\eta,d_{X},N^{\prime})$ is indeed a valid input
instance for the $r$-restricted $\mathsf{MaintainCluster}$ problem, in the
following simple but technical observation, whose proof is deferred to Section
B.1 of Appendix.

######  Observation 5.5.

$(H[X^{0}],\Delta,\eta,d_{X},N^{\prime})$ is a valid input to the
$r$-restricted $\mathsf{MaintainCluster}$ problem.

Recall that Algorithm ${\mathcal{A}}(X)$ may, at any time, produce a strongly
well-structured cut $(Y,Z)$ in $H[X]$ of sparsity
$\Phi_{H[X]}(Y,Z)\leq\frac{(\log N^{\prime})^{64}}{d_{X}}$. Below, we provide
an algorithm for processing such a cut. But before we do so, we provide the
remaining details for processing cluster $X$.

Recall that the algorithm for the $s$-$t$-SP problem consists of at most
$\Delta$ iterations. At the beginning of every iteration $i$, we will compute,
for every non-leaf regular cluster $X\in{\mathcal{X}}$, a pair $x,y\in V(X)$
of vertices (where possibly $x=y$). The corresponding algorithm
${\mathcal{A}}(X)$ is then required to compute a simple path $P_{X}$
connecting $x$ to $y$ in graph $H[X]$, whose length is at most $d_{X}$. We
will then process the resulting paths $P_{X}$ for all non-leaf clusters
$X\in{\mathcal{X}}$, in order to obtain a short $s$-$t$ path $P_{i}$ in $H$,
as required. For each non-leaf cluster $X\in{\mathcal{X}}$, we will ensure
that $E(P_{i})\cap E(H[X])\subseteq E(P_{X})$. Following that, the lengths of
some special edges on path $P_{i}$ may be doubled; we assume that our
algorithm is given the list of all such edges. In particular, for each non-
leaf regular cluster $X\in{\mathcal{X}}$, we are given a subset of the special
edges on path $P_{X}$, whose lengths must be doubled. From the definition of
the $s$-$t$-SP problem, we are guaranteed that, for every non-leaf regular
cluster $X\in{\mathcal{X}}$, for every special edge $e\in E(H[X])$, if
$\tau^{\prime}>\tau$ are two times at which the length of $e$ is doubled, then
the number of paths $P_{X}$ that Algorithm ${\mathcal{A}}(X)$ returned in
response to queries during the time interval $(\tau,\tau^{\prime}]$, which
contain $e$, is at least $\eta$, so Property P1 holds for the instance of the
$\mathsf{MaintainCluster}$ problem associated with $X$. If Algorithm
${\mathcal{A}}(X)$ ever returns “FAIL”, then we terminate our algorithm for
the $s$-$t$-SP problem, and return “FAIL” as well.

Lastly, whenever, for a non-leaf regular cluster $X\in{\mathcal{X}}$, $|X|$
falls below $\frac{|X^{0}|}{2}$, we terminate Algorithm ${\mathcal{A}}(X)$,
and we say that cluster $X$ is _destroyed_. We then think of the resulting set
$X$ of vertices as a new cluster that was just added to ${\mathcal{X}}$, and
treat it as such (so we think that, once cluster $X$ is destroyed, it is
deleted from ${\mathcal{X}}$, and instead a new cluster, that is identical to
$X$, is inserted into ${\mathcal{X}}$). It now remains to describe the
algorithm to process sparse cuts produced by Algorithm ${\mathcal{A}}(X)$ for
non-leaf regular clusters $X\in{\mathcal{X}}$.

#### Processing a Cut $(Y,Z)$ in Cluster $X$

We assume that we are given a non-leaf regular cluster $X\in{\mathcal{X}}$,
and a strongly well-structured cut $(Y,Z)$ in $H[X]$ of sparsity
$\Phi_{H[X]}(Y,Z)\leq\frac{(\log N^{\prime})^{64}}{d_{X}}$. We denote by
$J\subseteq Y$ and $J^{\prime}\subseteq Z$ the sets of vertices that serve as
endpoints of the edges of $E_{H}(Y,Z)$. Since the edges of $E_{H}(Y,Z)$ are
special edges, it must be the case that $J\subseteq R$ and
$J^{\prime}\subseteq L$. Denote $Y^{\prime}=Y\setminus J$ and
$Z^{\prime}=Z\setminus J^{\prime}$. We start with the following simple
observation, whose proof is deferred to Section B.2 of Appendix.

######  Observation 5.6.

Each of the graphs $H[Y^{\prime}],H[Z^{\prime}]$ is a perfect well-structured
graph.

Assume first that $w(Y)\leq w(Z)$. We update the set $X$ of vertices, by
deleting the vertices of $Y\cup J^{\prime}$ from it; in other words, we set
$X=Z^{\prime}$. We then add $Y^{\prime}$ as a new cluster to ${\mathcal{X}}$,
and additionally, for every vertex $v\in J\cup J^{\prime}$, we add a new
singleton cluster $\left\\{v\right\\}$ to ${\mathcal{X}}$. We define the
intervals associated with the new clusters, as follows. We assign, to every
vertex $v\in J^{\prime}\cup J$ an interval $I_{\left\\{v\right\\}}\subseteq
I_{X}$ of length $1$, and additionally we define two intervals:
$I_{Y^{\prime}}\subseteq I_{X}$ of length $|Y^{\prime}|$ and
$I_{Z^{\prime}}\subseteq I_{X}$ of length $|Z^{\prime}|$, so that all
resulting intervals
$I_{Y^{\prime}},I_{Z^{\prime}},\left\\{I_{\left\\{v\right\\}}\right\\}_{v\in
J\cup J^{\prime}}$ are mutually disjoint, and the intervals are ordered as
follows: we place the intervals corresponding to the vertices of $J^{\prime}$
first, followed by interval $I_{Z^{\prime}}$, then $I_{Y^{\prime}}$, and
lastly the intervals corresponding to the vertices of $J$. Since we have set
$X=Z^{\prime}$, we let $I_{X}=I_{Z^{\prime}}$. From 5.6, Invariant I1
continues to hold. We now show that Invariant I3 continues to hold, in the
following observation, whose proof is deferred to Section B.3 of Appendix.

######  Observation 5.7.

If $e=(u,v)$ is a right-to-left edge that was added due to the above
transformation of $\mathcal{ATO}$, then $u\in J$ and $v\in J^{\prime}$ holds,
and so $e\in E_{H}(Y,Z)$, and $e$ is a special edge.

Since we have defined a separate singleton cluster for every vertex of $J\cup
J^{\prime}$, from 5.7, Invariant I3 continues to hold. Moreover, the only
right-to-left edges that we have introduced during this update are the edges
of $E_{H}(Y,Z)$. Notice that the $\operatorname{span}(e)$ value of each such
edge is at most $|X|$. We call all edges of $E_{H}(Y,Z)$ _bad edges_ , and we
say that they are _owned_ by cluster $X$.

Recall that so far we have assumed that $w(Y)\leq w(Z)$. If $w(Y)>w(Z)$, then
the algorithm remains the same, except that at the end we update cluster $X$
by deleting the vertices of $Z\cup J$ from it; or equivalently, we set
$X=Y^{\prime}$. We also set $I_{X}=I_{Y^{\prime}}$. This concludes the
algorithm for processing the cut $(Y,Z)$ of a non-leaf regular cluster
$X\in{\mathcal{X}}$.

####  5.1.3 The Special Cluster

Recall that Case 1 happens if $|U^{0}|>2(n-|B^{0}|)\cdot(\log N)^{128}$ holds.
In this case, we let $U$ be the special cluster of the $\mathcal{ATO}$, and we
set $\gamma=|U^{0}|-256(n-|B^{0}|)(\log N)^{64}$. We now show an algorithm for
processing the special cluster $U$ if Case 1 happened. We initialize Algorithm
${\mathcal{A}}^{\prime}$ for the $r$-restricted
$\mathsf{MaintainSpecialCluster}$ problem on graph $H[U^{0}]$, with parameters
$\Delta$ and $\eta$ that remain unchanged, parameter $d$ replaced by parameter
$d_{U}=\max\left\\{(\log N^{\prime})^{64},\left(|U^{0}\setminus
B^{0}|+\Delta\right)\frac{\eta}{4\Delta\cdot 2^{\sqrt{\log N}}}\right\\}$, and
parameter $N$ replaced with $N^{\prime}$. We also initially set
$\beta=B^{0}\cap U^{0}$, and we ensure that, throughout the algorithm,
$\beta=B\cap U$ holds. In other words, whenever a vertex of $\beta$ is deleted
from $B$ or from $U$, it is also deleted from $\beta$.

We denote this instantiation of Algorithm ${\mathcal{A}}^{\prime}$ by
${\mathcal{A}}^{\prime}(U)$. We now verify that
$(H[U^{0}],\beta,\Delta,\eta,d,N^{\prime})$ is indeed a valid input instance
for the $r$-restricted $\mathsf{MaintainSpecialCluster}$ problem, in the
following simple observation, whose proof is deferred to Section B.4 of
Appendix.

######  Observation 5.8.

$(H[U^{0}],\beta,\Delta,\eta,d_{U},N^{\prime})$ is a valid input to the
$r$-restricted $\mathsf{MaintainSpecialCluster}$ problem.

Recall that Algorithm ${\mathcal{A}}^{\prime}(U)$ may, at any time, produce a
strongly well-structured cut $(Y,Z)$ in $H[U]$ of sparsity
$\Phi_{H[U]}(Y,Z)\leq\frac{(\log N^{\prime})^{64}}{d_{U}}$, such that
$w(Y)\geq 1.8|\beta\cap Y|$ holds. Below, we provide an algorithm for
processing such a cut. But before we do so, we provide the remaining details
for processing cluster $U$. We will show later that, throughout the algorithm,
$|\beta|\geq\frac{|B^{0}\cap U^{0}|}{2}$ holds.

Recall that the algorithm for the $s$-$t$-SP problem consists of at most
$\Delta$ iterations. At the beginning of every iteration $i$, we may compute a
single vertex $x\in U$, that is sent as a query to Algorithm
${\mathcal{A}}^{\prime}(U)$. Algorithm ${\mathcal{A}}^{\prime}(U)$ is then
required to compute a simple path $P(x)$ connecting $x$ to some vertex
$y\in\beta$ in graph $H[U]$, whose length is at most $d_{U}$, such that no
inner vertex of $P(x)$ lies in $\beta$ (if $x\in\beta$, then we require that
path $P(x)$ only consists of the vertex $x$). Our algorithm will then compute
a short $s$-$t$ path $P_{i}$ in $H$, as required, so that $E(P_{i})\cap
E(H[U])\subseteq E(P(x))$. Following that, the lengths of some special edges
on path $P_{i}$ may be doubled; we assume that our algorithm is given the list
of all such edges. In particular, we are given a subset of the special edges
on path $P(x)$, whose lengths must be doubled. Additionally, vertex $y$ that
serves as an endpoint of path $P(x)$ is deleted from set $B$ and from set
$\beta$. This ensures that the lengths of the special edges that are incident
to vertices of $\beta$ always remain $1$. We note that in some of the
iterations the algorithm for the $s$-$t$-SP problem may not ask any queries to
algorithm ${\mathcal{A}}^{\prime}(U)$, and in such iterations the lengths of
the special edges of $H[U]$ are not doubled. From the definition of the
$s$-$t$-SP problem, we are guaranteed that, for every special edge $e\in
E(H[U])$, if $\tau^{\prime}>\tau$ are two times at which the length of $e$ is
doubled, then the number of paths $P(x)$ that Algorithm
${\mathcal{A}}^{\prime}(U)$ returned in response to queries during the time
interval $(\tau,\tau^{\prime}]$, which contain $e$, is at least $\eta$, so
Property P1 holds for the instance of the $\mathsf{MaintainSpecialCluster}$
problem associated with $U$. If Algorithm ${\mathcal{A}}^{\prime}(U)$ ever
returns “FAIL”, then we terminate our algorithm for the $s$-$t$-SP problem,
and return “FAIL” as well.

Finally, we provide an algorithm for processing the sparse cuts that Algorithm
${\mathcal{A}}^{\prime}(U)$ may produce. Suppose Algorithm
${\mathcal{A}}^{\prime}(U)$ returns a strongly well-structured cut $(Y,Z)$ in
$H[U]$ of sparsity $\Phi_{H[U]}(Y,Z)\leq\frac{(\log N^{\prime})^{64}}{d_{U}}$,
such that $w(Y)\geq 1.8|\beta\cap Y|$ holds. We denote by $J\subseteq Y$ and
$J^{\prime}\subseteq Z$ the sets of vertices that serve as endpoints of the
edges of $E_{H}(Y,Z)$, and we let $Y^{\prime}=Y\setminus J$ and
$Z^{\prime}=Z\setminus J^{\prime}$. Using the same reasoning as in the proof
of 5.6, each of the graphs $H[Y^{\prime}],H[Z^{\prime}]$ is a perfect well-
structured graph. We will show below that $|Z^{\prime}|\geq\gamma$ must hold.
We delete the vertices of $Y\cup J^{\prime}$ from $U$, so that $U=Z^{\prime}$
now holds, and we add $Y^{\prime}$ as a new cluster to ${\mathcal{X}}$.
Additionally, for every vertex $v\in J\cup J^{\prime}$, we add a new singleton
cluster $\left\\{v\right\\}$ to ${\mathcal{X}}$. We define the intervals
associated with the new clusters as follows. We assign, to every vertex $v\in
J^{\prime}\cup J$ an interval $I_{\left\\{v\right\\}}\subseteq I_{U}$ of
length $1$, and additionally we define two intervals: $I_{Y^{\prime}}\subseteq
I_{U}$ of length $|Y^{\prime}|$ and $I_{Z^{\prime}}\subseteq I_{U}$ of length
$|Z^{\prime}|-\gamma+1$, so that all resulting intervals
$I_{Y^{\prime}},I_{Z^{\prime}},\left\\{I_{\left\\{v\right\\}}\right\\}_{v\in
J\cup J^{\prime}}$ are mutually disjoint, and the intervals are ordered as
follows: we place the intervals corresponding to the vertices of $J^{\prime}$
first, followed by interval $I_{Z^{\prime}}$, then $I_{Y^{\prime}}$, and
lastly the intervals corresponding to the vertices of $J$. Since we have set
$U=Z^{\prime}$, we let $I_{U}=I_{Z^{\prime}}$. As before, Invariant I1
continues to hold. Using the same reasoning as in the proof of 5.7, if
$e=(u,v)$ is a right-to-left edge that was added due to the above
transformation of $\mathcal{ATO}$, then $u\in J$ and $v\in J^{\prime}$ holds,
and so $e\in E_{H}(Y,Z)$, and $e$ is a special edge. In particular, Invariant
I3 continues to hold. Moreover, the only right-to-left edges that we have
introduced during this update are the edges of $E_{H}(Y,Z)$. Notice that the
$\operatorname{span}(e)$ value of each such edge is at most
$|U^{0}|-\gamma+1$. We call all edges of $E_{H}(Y,Z)$ _bad edges_ , and we say
that they are _owned_ by cluster $U$. We denote by $E^{\mathsf{bad}}(U)$ the
set of all bad edges that are owned by cluster $U$ over the course of the
algorithm. In the following observation we show that $|U|\geq\gamma$ holds
throughout the algorithm, and we bound $|E^{\mathsf{bad}}(U)|$.

######  Observation 5.9.

Over the course of the algorithm, at most $64|U^{0}\setminus
B^{0}|+128\Delta\cdot(\log N)^{64}\leq 256(n-|B^{0}|)(\log N)^{64}$ vertices
are deleted from $U$, and so throughout the algorithm, $|U|\geq\gamma$ and
$|\beta|\geq\frac{|U^{0}\cap B^{0}|}{2}$ hold. Moreover,
$|E^{\mathsf{bad}}(U)|\leq\frac{\Delta\cdot 2^{6\sqrt{\log N}}}{\eta}$.

###### Proof.

Recall that we denoted by $E^{*}\subseteq E^{\mathsf{spec}}$ the set of all
special edges $e=(u,v)$, such that $u,v\in B$ holds at the end of the
algorithm. Let $B^{*}\subseteq B$ the set of vertices containing all endpoints
of the edges in $E^{*}$, and let $\tilde{U}=U^{0}\setminus B^{*}$. For every
vertex $v\in U^{0}$, we define a weight $\tilde{w}(v)$ as follows: if, at the
end of the algorithm, $v\in U$, then $\tilde{w}(v)$ is the weight of $v$ at
the end of the algorithm; otherwise, $\tilde{w}(v)$ is the weight of $v$ just
before it is deleted from $U$. We use the following observation, whose proof
is very similar to the proof of 5.3, and deferred to Section B.5 of Appendix.

######  Observation 5.10.

$\sum_{v\in\tilde{U}}\tilde{w}(v)\leq 8|U^{0}\setminus
B^{0}|+8\Delta\cdot(\log N^{\prime})^{64}$.

Consider now some cut $(Y,Z)$ of $U$ that Algorithm
${\mathcal{A}}^{\prime}(U)$ produced. Recall that $|E_{H}(Y,Z)|\leq\frac{(\log
N^{\prime})^{64}}{d_{U}}\cdot w(Y)$, and that $w(Y)\geq 1.8|\beta\cap Y|$
holds. Since $B^{*}\cap Y\subseteq\beta\cap Y$, we get that $w(Y)\geq
1.8|B^{*}\cap Y|$. Since the weight of every vertex in $B^{*}$ remains $1$
throughout the algorithm, we get that $w(Y\setminus B^{*})=w(Y)-|B^{*}\cap
Y|\geq w(Y)-\frac{w(Y)}{1.8}\geq 0.44w(Y)$. In particular, $|Y\cap
B^{*}|\leq\frac{w(Y)}{1.8}\leq\frac{w(Y\setminus B^{*})}{1.8\cdot 0.44}\leq
1.3w(Y\setminus B^{*})$.

Moreover, $|Y|\leq w(Y)=w(Y\setminus B^{*})+|Y\cap B^{*}|\leq 2.3w(Y\setminus
B^{*})$ holds. Recall that all vertices of $Y$, and also the endpoints of the
special edges in $E_{H}(Y,Z)$ are deleted from cluster $U$ following the cut
$(Y,Z)$. Therefore, the total number of vertices deleted from $U$ following
the cut $(Y,Z)$ is at most $2|Y|\leq 4.6w(Y\setminus B^{*})\leq 4.6\sum_{v\in
Y\cap\tilde{U}}\tilde{w}(v)$. Lastly:

$|E_{H}(Y,Z)|\leq\frac{(\log N^{\prime})^{64}}{d_{U}}\cdot w(Y)\leq\frac{(\log
N^{\prime})^{64}}{d_{U}}\cdot 2.3w(Y\setminus B^{*})\leq\frac{2.3\cdot(\log
N^{\prime})^{64}}{d_{U}}\cdot\sum_{v\in Y\cap\tilde{U}}\tilde{w}(v).$

Consider now all cuts $(Y_{1},Z_{1}),\ldots,(Y_{r},Z_{r})$ that Algorithm
${\mathcal{A}}^{\prime}(U)$ ever produced, in the order in which they were
produced. For all $1\leq i\leq r$, following the cut $(Y_{i},Z_{i})$, the
vertices of $Y_{i}$, along with some additional vertices, were deleted from
$U$. From the above discussion, the total number of vertices deleted from $U$
following the cut is bounded by $4.6\sum_{v\in
Y_{i}\cap\tilde{U}}\tilde{w}(v)$, and
$|E_{H}(Y_{i},Z_{i})|\leq\frac{2.3\cdot(\log
N^{\prime})^{64}}{d_{U}}\cdot\sum_{v\in Y\cap\tilde{U}}\cdot\sum_{v\in
Y_{i}\cap\tilde{U}}\tilde{w}(v)$. We conclude that the total number of
vertices deleted from $U$ over the course of the algorithm is bounded by:

$\begin{split}4.6\sum_{i=1}^{r}\sum_{v\in Y_{i}\cap\tilde{U}}\tilde{w}(v)&\leq
4.6\sum_{v\in\tilde{U}}\tilde{w}(v)\\\ &\leq 64|U^{0}\setminus
B^{0}|+64\Delta\cdot(\log N^{\prime})^{64}\\\ &\leq 64|U^{0}\setminus
B^{0}|+128\Delta\cdot(\log N)^{64}\\\ &\leq 256(n-|B^{0}|)(\log
N)^{64},\end{split}$

from Inequality 3. Since, at the beginning of the algorithm,
$|U|>2(n-|B^{0}|)\cdot(\log N)^{128}$ holds, and since
$\gamma=|U^{0}|-256(n-|B^{0}|)(\log N)^{64}$, we get that $|U|\geq\gamma$
holds throughout the algorithm.

Next, we show that, throughout the algorithm, $|\beta|\geq\frac{|U^{0}\cap
B^{0}|}{2}$ holds. Recall again that $|U^{0}|>2(n-|B^{0}|)\cdot(\log
N)^{128}$, and that $|U^{0}\setminus B^{0}|\leq n-|B^{0}|$. Therefore,
$|U^{0}\cap B^{0}|\geq|U^{0}|-|U^{0}\setminus B^{0}|\geq(n-|B^{0}|)\cdot(\log
N)^{128}$. Set $\beta$ contains all vertices of $U^{0}\cap B^{0}$, except for
the vertices that were deleted from $B$ (whose number is bounded by
$\Delta\leq n-|B^{0}|$), and the vertices that were deleted from $U$ (whose
number is bounded by $256(n-|B^{0}|)(\log N)^{64}$). Therefore, throughout the
algorithm, $|\beta|\geq|U^{0}\cap B^{0}|-257(n-|B^{0}|)(\log N)^{64}$ must
hold. Since $|U^{0}\cap B^{0}|\geq(n-|B^{0}|)\cdot(\log N)^{128}$, we get that
$|\beta|\geq\frac{|U^{0}\cap B^{0}|}{2}$ holds throughout the algorithm.

Lastly, we get that:

$\begin{split}|E^{\mathsf{bad}}(U)|&\leq\sum_{i=1}^{r}|E_{H}(Y_{i},Z_{i})|\\\
&\leq\frac{2.3\cdot(\log N^{\prime})^{64}}{d_{U}}\cdot\sum_{i=1}^{r}\sum_{v\in
Y\cap\tilde{U}}\tilde{w}(v)\\\ &\leq\frac{10\Delta\cdot 2^{2\sqrt{\log
N^{\prime}}}}{\left(|U^{0}\setminus
B^{0}|+\Delta\right)\cdot\eta}\cdot\sum_{v\in\tilde{U}}\tilde{w}(v)\\\
&\leq\frac{10\Delta\cdot 2^{2\sqrt{\log N^{\prime}}}}{\left(|U^{0}\setminus
B^{0}|+\Delta\right)\cdot\eta}\cdot\left(8|U^{0}\setminus B^{0}|+8\Delta(\log
N^{\prime})^{64}\right)\\\ &\leq\frac{\Delta\cdot 2^{6\sqrt{\log
N}}}{\eta},\end{split}$

since $d_{U}=\max\left\\{(\log N^{\prime})^{64},\left(|U^{0}\setminus
B^{0}|+\Delta\right)\frac{\eta}{4\Delta\cdot 2^{\sqrt{\log
N}}}\right\\}\geq\left(|U^{0}\setminus
B^{0}|+\Delta\right)\frac{\eta}{4\Delta\cdot 2^{\sqrt{\log N}}}$; we have also
used Inequality 4.

####  5.1.4 Child Clusters, Descendant Clusters, and a Useful Bound

Let $\tilde{\mathcal{X}}$ denote the set of all clusters that ever belonged to
${\mathcal{X}}$ over the course of the algorithm. We partition
$\tilde{\mathcal{X}}$ into three subsets: set $\tilde{\mathcal{X}}_{0}$
contains all singleton clusters, set $\tilde{\mathcal{X}}_{1}$ contains all
non-singleton leaf clusters, and set $\tilde{\mathcal{X}}_{2}$ contains all
non-leaf clusters. If the special cluster is defined, then we set
$\tilde{\mathcal{X}}_{2}^{\prime}=\tilde{\mathcal{X}}_{2}\setminus\left\\{U\right\\}$,
and otherwise we let
$\tilde{\mathcal{X}}_{2}^{\prime}=\tilde{\mathcal{X}}_{2}$.

Let $E^{\mathsf{bad}}$ be the set of all edges of $G$ that ever served as
right-to-left edges of the $\mathcal{ATO}$. For every cluster
$X\in\tilde{\mathcal{X}}_{1}\cup\tilde{\mathcal{X}}_{2}$, we denote by
$E^{\mathsf{bad}}(X)$ the set of all bad edges that cluster $X$ owns. Recall
that, once an edge $e=(x,y)$ is added to the set $E^{\mathsf{bad}}(X)$ of
edges, its initial value $\operatorname{span}(e)$ is bounded by $|X|$. From
Invariant I3, once edge $e$ was added to set $E^{\mathsf{bad}}$, if
$Y,Y^{\prime}$ were the clusters of ${\mathcal{X}}$ containing $x$ and $y$
respectively, then $Y=\left\\{x\right\\}$ and $Y^{\prime}=\left\\{y\right\\}$
holds. In other words, when $e$ was added to $E^{\mathsf{bad}}$, $Y$ and
$Y^{\prime}$ were singleton clusters. Therefore, these clusters, and their
corresponding intervals $I_{Y}$ and $I_{Y^{\prime}}$, remain unchanged for the
remainder of the algorithm. In particular, the value $\operatorname{span}(e)$
also remains unchanged for the remainder of the algorithm.

Recall that, from Invariant I1, for every cluster
$X\in\tilde{\mathcal{X}}_{2}^{\prime}$, graph $H[X]$ remains a perfect well-
structured graph for as long as $X$ lies in ${\mathcal{X}}$. Recall also that
we have defined weights of vertices for such graphs: for every vertex $v\in
X$, its weight $w(v)$ is the length of the unique special edge incident to $v$
in $H[X]$. As the algorithm progresses, the lengths of some special edges
grow, and so do the weights of the vertices in $H[X]$. For every vertex $v\in
X^{0}$, we denote by $w^{0}_{X}(v)$ the weight of $v$ when cluster $X$ was
first added to set ${\mathcal{X}}$, and algorithm ${\mathcal{A}}(X)$ was
initialized. If $v$ belongs to set $X$ when algorithm ${\mathcal{A}}(X)$ is
terminated (e.g. because $|X|$ fell below $|X^{0}|/2$), then we let
$w^{*}_{X}(v)$ denote the weight of $v$ in graph $H[X]$ when algorithm
${\mathcal{A}}(X)$ terminated. Otherwise, we denote by $w^{*}_{X}(v)$ the
weight of $v$ just before it was deleted from $X$. We also denote
$W^{0}(X)=\sum_{v\in X^{0}}w^{0}_{X}(v)$, and $W^{*}(X)=\sum_{v\in
X^{0}}w^{*}_{X}(v)$. From 5.3, the total length of all edges in
$E^{\mathsf{spec}}$ at the end of the algorithm is bounded by
$|E^{\mathsf{spec}}|+2(n-|B^{0}|)\log^{5}n\leq 4n\log^{5}n$, and so, for every
cluster $X\in\tilde{\mathcal{X}}_{2}$:

$W^{0}(X)\leq W^{*}(X)\leq 8n\log^{5}n.$ (6)

Recall that, at the beginning of the algorithm, ${\mathcal{X}}$ may contain at
most one non-leaf cluster – the cluster $U$. A new non-leaf cluster
$X^{\prime}$ may only be inserted into ${\mathcal{X}}$ in one of the following
two cases: (i) there is some existing non-leaf cluster $X\in{\mathcal{X}}$,
for which $|X|$ fell below $|X^{0}|/2$, and $X^{\prime}=X$; or (ii) there is
some existing non-leaf cluster $X\in{\mathcal{X}}$, for which Algorithm
${\mathcal{A}}(X)$ or ${\mathcal{A}}^{\prime}(X)$ just computed a sparse well-
structured cut $(Y,Z)$, and $X^{\prime}$ is contained in one of the sets $Y$
or $Z$. In the latter case, the vertices of $X^{\prime}$ (along, possibly,
with some additional vertices) are deleted from $X$. In either one of the
above two cases, we say that $X$ is the _parent-cluster_ of $X^{\prime}$, and
$X^{\prime}$ is the _child-cluster_ of $X$. We can now naturally define a
descendant-ancestor relationship between clusters: Cluster $X^{\prime}$ is a
descendant-cluster of another cluster $X$, iff there is a sequence
$X^{\prime}=X_{1},X_{2},\ldots,X_{r}=X$ of $r\geq 1$ clusters, such that, for
all $1\leq i<r$, $X_{i}$ is a child-cluster of $X_{i+1}$. If $X^{\prime}$ is a
descendant-cluster of $X$, then $X$ is the ancestor-cluster of $X^{\prime}$.
It is easy to verify that, for every pair
$X_{1},X_{2}\in\tilde{\mathcal{X}}_{2}$ of clusters, either $X^{0}_{1}\cap
X^{0}_{2}=\emptyset$, or $X_{1}^{0}\subseteq X^{0}_{2}$ (in which case $X_{1}$
is a descendant cluster of $X_{2}$), or $X_{2}^{0}\subseteq X^{0}_{1}$ (in
which case $X_{2}$ is a descendant cluster of $X_{1}$). From the above
discussion, if $X_{1}$ is a child-cluster of some cluster
$X_{2}\in{\mathcal{X}}^{\prime}_{2}$, then either $|X_{1}^{0}|<|X_{2}^{0}|/2$;
or, at the time when $X_{1}$ was created, $\sum_{v\in X_{1}}w(v)\leq\sum_{v\in
X_{2}}w(v)/2$ held, following which the vertices of $X_{1}$ were deleted from
$X_{2}$.

Consider now a pair $X_{1},X_{2}\in\tilde{\mathcal{X}}_{2}^{\prime}$ of
clusters, where $X_{2}$ is a descendant cluster of $X_{1}$. We say that
$X_{2}$ is a _close descendant of $X_{1}$_ iff $|X_{2}^{0}|>|X_{1}^{0}|/2$. In
the following claim, we bound the number of close descendants of every cluster
in $\tilde{X}_{2}^{\prime}$. The proof is somewhat technical and deferred to
Section B.6 of Appendix.

######  Claim 5.11.

Every cluster $X\in\tilde{X}_{2}^{\prime}$ has at most $64\left\lceil\log
n\right\rceil$ close descendants.

For the sake of analysis, we need to bound
$\sum_{X\in\tilde{\mathcal{X}}_{2}^{\prime}}W^{*}(X)$. This bound will later
be used both in order to bound the running time of the algorithm, and in order
to bound $\sum_{e\in E^{\mathsf{bad}}}\operatorname{span}(e)$.

######  Observation 5.12.

$\sum_{X\in\tilde{\mathcal{X}}_{2}^{\prime}}W^{*}(X)\leq(n-|B^{0}|)\cdot(\log
N)^{133}$.

###### Proof.

Recall that for every cluster $X\in\tilde{\mathcal{X}}^{\prime}_{2}$,
$W^{0}(X)\leq 8n\log^{5}n$ holds (see Inequality 6). For all $0\leq
i<\left\lceil\log n\right\rceil$ and $0\leq j\leq 4\left\lceil\log
n\right\rceil$, we denote by ${\mathcal{X}}_{i,j}$ the set of all clusters
$X\in\tilde{\mathcal{X}}^{\prime}_{2}$ with $2^{i}\leq|X^{0}|<2^{i+1}$ and
$2^{j}\leq W^{0}(X)<2^{j+1}$.

Fix a pair $0\leq i<\left\lceil\log n\right\rceil$ and $0\leq j\leq
4\left\lceil\log n\right\rceil$ of indices, and consider the collection
${\mathcal{X}}_{i,j}$ of clusters. Notice that, if
$X,X^{\prime}\in{\mathcal{X}}_{i,j}$, and $X^{\prime}$ is a descendant-cluster
of $X$, then $X^{\prime}$ is a close descendant of $X$. From 5.11, for every
cluster $X\in{\mathcal{X}}_{i,j}$, at most $64\left\lceil\log n\right\rceil$
descendant clusters of $X$ lie in ${\mathcal{X}}_{i,j}$. Using a simple greedy
algorithm, we can then paratition the clusters in ${\mathcal{X}}_{i,j}$ into
$z=64\left\lceil\log n\right\rceil+1$ subsets
${\mathcal{Y}}_{1},\ldots,{\mathcal{Y}}_{z}$, such that, for all $1\leq
z^{\prime}\leq z$, for every pair $X,X^{\prime}\in{\mathcal{Y}}_{z^{\prime}}$
of clusters, neither of the two clusters is a descendant of the other. In
order to do so, we consider the clusters $X\in{\mathcal{X}}_{i,j}$ one by one,
in the non-decreasing order of $|X^{0}|$, breaking ties arbitrarily. When
cluster $X$ is considered, there must be some index $1\leq z^{\prime}\leq z$,
such that no descendant of $X$ lies in ${\mathcal{Y}}_{z^{\prime}}$, and we
add $X$ to such a set ${\mathcal{Y}}_{z^{\prime}}$. For all $1\leq
z^{\prime}\leq z$, we now bound
$\sum_{X\in{\mathcal{Y}}_{z^{\prime}}}W^{*}(X)$ separately.

Fix any index $1\leq z^{\prime}\leq z$, and denote
${\mathcal{Y}}^{\prime}=\left\\{X^{0}\mid
X\in{\mathcal{Y}}_{z^{\prime}}\right\\}$. Since, for every pair $X,X^{\prime}$
of clusters in ${\mathcal{Y}}_{z^{\prime}}$, neither is the descendant of the
other, all sets in ${\mathcal{Y}}^{\prime}$ are mutually disjoint.

Assume first that Case 2 happened, so the special cluster is undefined, and
$|U^{0}|\leq 2(n-|B^{0}|)\cdot(\log N)^{128}$ holds. From the construction of
the set $U$ of vertices at the beginning of the algorithm, for every special
edge $e\in E^{\mathsf{spec}}$, both endpoints of $e$ lie in $U^{0}$.
Therefore, $|E^{\mathsf{spec}}|\leq\frac{|U^{0}|}{2}\leq(n-|B^{0}|)\cdot(\log
N)^{128}$. From 5.3, the total length of all edges in $E^{\mathsf{spec}}$ at
the end of the algorithm is bounded by
$|E^{\mathsf{spec}}|+2(n-|B^{0}|)\log^{5}n\leq(n-|B^{0}|)\cdot(\log N)^{129}$.
Since the clusters in ${\mathcal{Y}}^{\prime}$ are mutually disjoint, it is
easy to verify that $\sum_{X\in{\mathcal{Y}}_{z^{\prime}}}W^{*}(X)\leq
2(n-|B^{0}|)\cdot(\log N)^{129}$.

Next, we consider Case 1, where the special cluster is defined. Let $U^{*}$
denote the set $U$ of vertices at the end of the algorithm. Notice that
$U^{*}$ is disjoint from all sets of vertices in ${\mathcal{Y}}^{\prime}$. For
every vertex $v\in U^{*}$, let $w^{*}(v)$ be the weight of $v$ at the end of
the algorithm, and let $W^{*}(U)=\sum_{v\in U^{*}}w^{*}(v)$. From 5.3, the
total length of all edges in $E^{\mathsf{spec}}$ at the end of the algorithm
is bounded by $|E^{\mathsf{spec}}|+2(n-|B^{0}|)\log^{5}n$, and so:

$\sum_{X\in{\mathcal{Y}}_{z^{\prime}}}W^{*}(X)+W^{*}(U)\leq
2|E^{\mathsf{spec}}|+4(n-|B^{0}|)\log^{5}n.$ (7)

Recall that all vertices that serve as endpoints of the edges in
$E^{\mathsf{spec}}$ lie in $U^{0}$. From 5.9, $|U^{0}\setminus U^{*}|\leq
256(n-|B^{0}|)\cdot(\log N)^{64}$. Therefore, $|U^{*}|\geq
2|E^{\mathsf{spec}}|-256(n-|B^{0}|)\cdot(\log N)^{64}$, and
$W^{*}(U)\geq|U^{*}|\geq 2|E^{\mathsf{spec}}|-256(n-|B^{0}|)\cdot(\log
N)^{64}$. Combining this with Inequality 7, we get that:

$\sum_{X\in{\mathcal{Y}}_{z^{\prime}}}W^{*}(X)\leq
2|E^{\mathsf{spec}}|+4(n-|B^{0}|)\log^{5}n-W^{*}(U)\leq
260(n-|B^{0}|)\cdot(\log N)^{64}\leq 2(n-|B^{0}|)\cdot(\log N)^{129}.$

To conclude, we have shown that, for every index $1\leq z^{\prime}\leq z$:

$\sum_{X\in{\mathcal{Y}}_{z^{\prime}}}W^{*}(X)\leq 2(n-|B^{0}|)\cdot(\log
N)^{129}.$

Summing this up over all indices $1\leq z^{\prime}\leq z$, and recalling that
$z=64\left\lceil\log n\right\rceil+1\leq 128\log n$, we get that:

$\sum_{X\in{\mathcal{X}}_{i,j}}W^{*}(X)\leq 256(n-|B^{0}|)\cdot(\log
N)^{130}.$

Lastly, by summing up the above inequality over all indices $0\leq
i<\left\lceil\log n\right\rceil$ and $0\leq j\leq 4\left\lceil\log
n\right\rceil$, we get that:

$\sum_{X\in\tilde{\mathcal{X}}^{\prime}_{2}}W^{*}(X)\leq
2^{12}(n-|B^{0}|)\cdot(\log N)^{132}\leq(n-|B^{0}|)\cdot(\log N)^{133}.$

We obtain the following corollary of 5.12, that allows us to bound the total
span of all bad edges owned by the clusters in
$\tilde{\mathcal{X}}_{2}^{\prime}$.

######  Corollary 5.13.

$\sum_{X\in\tilde{\mathcal{X}}_{2}^{\prime}}\sum_{e\in
E^{\mathsf{bad}}(X)}\operatorname{span}(e)\leq\frac{(n-|B^{0}|)\cdot\Delta\cdot
2^{4\sqrt{\log N}}}{\eta}$.

###### Proof.

Consider a cluster $X\in{\mathcal{X}}_{2}^{\prime}$, and let $(Y,Z)$ be a cut
that Algorithm ${\mathcal{A}}(X)$ returned. Recall that
$|E_{H}(Y,Z)|\leq\frac{(\log
N^{\prime})^{64}}{d_{X}}\cdot\min\left\\{w(Y),w(Z)\right\\}$. If $w(Y)\leq
w(Z)$, then let $Z^{\prime}=Y$, and otherwise let $Z^{\prime}=Z$. Then
$|E_{H}(Y,Z)|\leq\frac{(\log N^{\prime})^{64}}{d_{X}}\cdot
w(Z^{\prime})\leq\frac{(\log N^{\prime})^{64}}{d_{X}}\cdot\sum_{v\in
Z^{\prime}}w^{*}_{X}(v)$ holds. Moreover, all vertices of $Z^{\prime}$ are
deleted from $X$ following the cut $(Y,Z)$, and the edges of $E_{H}(Y,Z)$ are
added to the set $E^{\mathsf{bad}}(X)$ of bad edges that $X$ owns. We assign
to every vertex $v\in Z^{\prime}$ a _charge_ of $\frac{(\log
N^{\prime})^{64}}{d_{X}}\cdot w^{*}_{X}(v)$ units, so that the total charge
assigned to the vertices of $Z^{\prime}$ is at least $|E_{H}(Y,Z)|$. It is
then easy to see that, at the end of Algorithm ${\mathcal{A}}(X)$, the total
number of edges in $E^{\mathsf{bad}}(X)$ is bounded by the total charge to all
vertices of $X^{0}$, which, in turn, is bounded by:

$\frac{(\log N^{\prime})^{64}}{d_{X}}\cdot\sum_{v\in
X^{0}}w^{*}_{X}(v)=\frac{(\log N^{\prime})^{64}}{d_{X}}\cdot W^{*}(X).$

Next, we show that $d_{X}\geq\frac{|X^{0}|\cdot\eta}{\Delta\cdot
2^{2\sqrt{\log N}}}$. Indeed, recall that
$d=\frac{(n-|B^{0}|)\cdot\eta}{4\Delta\cdot 2^{\sqrt{\log N}}}$ and so:

$d_{X}=\min\left\\{\frac{|X^{0}|\cdot\eta}{\Delta},d\right\\}=\min\left\\{\frac{|X^{0}|\cdot\eta}{\Delta},\frac{(n-|B^{0}|)\cdot\eta}{4\Delta\cdot
2^{\sqrt{\log N}}}\right\\}.$ (8)

If Case 2 happened, then $|U^{0}|\leq 2(n-|B^{0}|)\cdot(\log N)^{128}$, and,
since $X^{0}\subseteq U^{0}$, we get that $|X^{0}|\leq 2(n-|B^{0}|)\cdot(\log
N)^{128}$. If Case 1 happened, then, from 5.9, $|X^{0}|\leq
256(n-|B^{0}|)(\log N)^{64}$. Therefore, in any case, $|X^{0}|\leq
2(n-|B^{0}|)\cdot(\log N)^{128}$ must hold. Substituting the bound
$n-|B^{0}|\geq\frac{|X^{0}|}{2(\log N)^{128}}$ into Inequality 8, we get that
$d_{X}\geq\frac{|X^{0}|\cdot\eta}{\Delta\cdot 2^{2\sqrt{\log N}}}$.
Altogether, we get that:

$|E^{\mathsf{bad}}(X)|\leq\frac{(\log N^{\prime})^{64}}{d_{X}}\cdot
W^{*}(X)\leq\frac{\Delta\cdot 2^{2\sqrt{\log N}}\cdot(\log
N^{\prime})^{64}}{|X^{0}|\cdot\eta}\cdot W^{*}(X)\leq\frac{\Delta\cdot
2^{3\sqrt{\log N}}}{|X^{0}|\cdot\eta}\cdot W^{*}(X).$

Since for every edge $e\in E^{\mathsf{bad}}(X)$,
$\operatorname{span}(e)\leq|X^{0}|$, we get that:

$\sum_{e\in
E^{\mathsf{bad}}(X)}\operatorname{span}(e)\leq|X^{0}|\cdot|E^{\mathsf{bad}}(X)|\leq\frac{\Delta\cdot
2^{3\sqrt{\log N}}}{\eta}\cdot W^{*}(X).$

Finally, from 5.12:

$\begin{split}\sum_{X\in\tilde{\mathcal{X}}_{2}^{\prime}}\sum_{e\in
E^{\mathsf{bad}}(X)}\operatorname{span}(e)&\leq\frac{\Delta\cdot
2^{3\sqrt{\log
N}}}{\eta}\cdot\sum_{X\in\tilde{\mathcal{X}}_{2}^{\prime}}W^{*}(X)\\\
&\leq\frac{(n-|B^{0}|)\cdot\Delta\cdot 2^{3\sqrt{\log N}}\cdot(\log
N)^{133}}{\eta}\\\ &\leq\frac{(n-|B^{0}|)\cdot\Delta\cdot 2^{4\sqrt{\log
N}}}{\eta}.\end{split}$

####  5.1.5 Bounding the Running Time of Part 1 and Probability of Failure

Recall that, for every cluster $X\in\tilde{\mathcal{X}}^{\prime}_{2}$, the
total running time of Algorithm ${\mathcal{A}}(X)$ is bounded by:

$\begin{split}&c_{1}\cdot(W^{0}(X))^{2}\cdot 2^{c_{2}\sqrt{\log
N^{\prime}}}\cdot(\log N^{\prime})^{16c_{2}r}+c_{1}\cdot
W^{0}(X)\cdot\Delta\cdot\log^{4}N^{\prime}\\\
&\quad\quad\quad\quad\quad\quad\leq c_{1}\cdot
W^{0}(X)\cdot(W^{0}(X)+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+6}\cdot\left(1+\frac{1}{64c_{2}r}\right)^{16c_{2}r}\\\
&\quad\quad\quad\quad\quad\quad\leq c_{1}\cdot
W^{0}(X)\cdot(W^{0}(X)+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+7}.\end{split}$

(We have used the fact that, from Inequality 4, $2^{\sqrt{\log
N^{\prime}}}\leq 2^{\sqrt{\log N}}\cdot\log^{6}N$, and from Inequality 3,
$\log N^{\prime}\leq\left(1+\frac{1}{64c_{2}r}\right)\cdot\log N$.
Additionally, we used the assumption that $N$ is sufficiently large.).

Summing up over all clusters $X\in\tilde{\mathcal{X}}_{2}^{\prime}$, from
5.12, we get that the total running time of all Algorithm ${\mathcal{A}}(X)$
for clusters $X\in\tilde{\mathcal{X}}^{\prime}_{2}$ is bounded by:

$\begin{split}&\sum_{X\in\tilde{\mathcal{X}}_{2}^{\prime}}c_{1}\cdot
W^{0}(X)\cdot(W^{0}(X)+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+7}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq\left(\Delta\cdot\sum_{X\in\tilde{\mathcal{X}}^{\prime}_{2}}W^{0}(X)+\left(\sum_{X\in\tilde{\mathcal{X}}^{\prime}_{2}}W^{0}(X)\right)^{2}\right)\cdot
c_{1}\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}r+7}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq c_{1}\cdot(n-|B^{0}|)^{2}\cdot
2^{c_{2}\sqrt{\log N}}\cdot(\log N)^{16c_{2}r+273}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq c_{1}\cdot
n\cdot(n-|B^{0}|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+273}.\end{split}$

(We have used the fact that $\Delta\leq n-|B^{0}|$ from the problem
definition).

Assume now that Case 1 happened. In this case, the running time of Algorithm
${\mathcal{A}}^{\prime}(U)$ is bounded by:

$\begin{split}&c_{1}\cdot W^{0}(U)\cdot(W^{0}(U)-|\beta|+\Delta)\cdot
2^{c_{2}\sqrt{\log N^{\prime}}}\cdot(\log N^{\prime})^{16c_{2}r}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq c_{1}\cdot
W^{0}(U)\cdot(W^{0}(U)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+6}\cdot\left(1+\frac{1}{64c_{2}r}\right)^{16c_{2}r}\\\
&\quad\quad\quad\quad\quad\quad\quad\quad\leq c_{1}\cdot
W^{0}(U)\cdot(W^{0}(U)-|\beta|+\Delta)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+7}\\\ &\quad\quad\quad\quad\quad\quad\quad\quad\leq 2c_{1}\cdot
n\cdot(n-|B^{0}|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+7}.\end{split}$

(As before, we have used the fact that, from Inequality 4, $2^{\sqrt{\log
N^{\prime}}}\leq 2^{\sqrt{\log N}}\cdot\log^{6}N$, and from Inequality 3,
$\log N^{\prime}\leq\left(1+\frac{1}{64c_{2}r}\right)\cdot\log N$.
Additionally, since, at the beginning of the algorithm, the length of every
special edge is $1$, $W^{0}(U)=|U^{0}|\leq n$. From the problem definition,
$\Delta\leq n-|B^{0}|$, and it is easy to see that
$W^{0}(U)-|\beta|=|U^{0}|-|\beta|\leq n-|B^{0}|$ must hold).

Additional time that is required in order to maintain the $\mathcal{ATO}$ is
asymptotically bounded by the total number of edges that are ever present in
$H$, which, from the problem definition, is bounded by $O(|E(H)|)\leq
O(n\cdot(n-|B^{0}|))$. Overall, since we can assume that $c_{2}$ is a large
enough constant, the running time of Part 1 of the algorithm is bounded by:

$c_{1}\cdot n\cdot(n-|B^{0}|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+c_{2}}.$

Notice that, since $N\geq n$ is large enough, the above running time is also
bounded by $N^{3}$. Therefore, the total number of clusters that ever lie in
${\mathcal{X}}$ is also bounded by $N^{3}$. For each regular non-leaf cluster
$X\in\tilde{\mathcal{X}}$, the probability that Algorithm ${\mathcal{A}}(X)$
returns “FAIL” is bounded by $\frac{1}{(N^{\prime})^{4}}\leq\frac{1}{N^{4}}$.
If Case 1 happens, then the probability that Algorithm
${\mathcal{A}}^{\prime}(U)$ returns “FAIL” is bounded by $\frac{1}{4}$. From
the union bound, the total probability that our algorithm ever returns “FAIL”
is bounded by $\frac{1}{2}$, as required.

####  5.1.6 Bounding the Total Span of Bad Edges

Recall that, from Corollary 5.13,
$\sum_{X\in\tilde{\mathcal{X}}_{2}^{\prime}}\sum_{e\in
E^{\mathsf{bad}}(X)}\operatorname{span}(e)\leq\frac{(n-|B^{0}|)\cdot\Delta\cdot
2^{4\sqrt{\log N}}}{\eta}$.

If Case 1 happened, then, from 5.9,
$|E^{\mathsf{bad}}(U)|\leq\frac{\Delta\cdot 2^{6\sqrt{\log N}}}{\eta}$. It is
easy to verify that, for every edge $e\in E^{\mathsf{bad}}(U)$,
$\operatorname{span}(e)\leq|U^{0}|-\gamma\leq 256(n-|B^{0}|)(\log N)^{64}$,
since $\gamma=|U^{0}|-256(n-|B^{0}|)(\log N)^{64}$. Therefore, $\sum_{e\in
E^{\mathsf{bad}}(U)}\operatorname{span}(e)\leq\frac{\Delta\cdot 2^{6\sqrt{\log
N}}}{\eta}\cdot 256(n-|B^{0}|)(\log
N)^{64}\leq\frac{(n-|B^{0}|)\cdot\Delta\cdot 2^{7\sqrt{\log N}}}{\eta}$.

Lastly, consider a leaf cluster $X\in\tilde{\mathcal{X}}_{1}$, and recall that
$|X^{0}|\leq\frac{\Delta\cdot(\log N)^{128}}{\eta}$. Recall that
$|E^{\mathsf{bad}}(X)|\leq|X^{0}|$, and so $\sum_{e\in
E^{\mathsf{bad}}(X)}\operatorname{span}(e)\leq|X^{0}|^{2}\leq|X^{0}|\cdot\frac{\Delta\cdot(\log
N)^{128}}{\eta}$.

Note that all clusters in $\tilde{\mathcal{X}}_{1}$ are mutually disjoint,
and, for each such cluster $X$, $X^{0}\subseteq U^{0}$ holds. If Case 2
happened, then $|U^{0}|\leq 2(n-|B^{0}|)\cdot(\log N)^{128}$, and so
$\sum_{X\in\tilde{\mathcal{X}}_{1}}|X^{0}|\leq|U^{0}|\leq
2(n-|B^{0}|)\cdot(\log N)^{128}$. Otherwise, from 5.9,
$\sum_{X\in\tilde{\mathcal{X}}_{1}}|X^{0}|\leq 256(n-|B^{0}|)(\log N)^{64}$.
Therefore, in either case, $\sum_{X\in\tilde{\mathcal{X}}_{1}}|X^{0}|\leq
2(n-|B^{0}|)\cdot(\log N)^{128}$ holds, and so overall:

$\sum_{X\in\tilde{\mathcal{X}}_{1}}\sum_{e\in
E^{\mathsf{bad}}(X)}\operatorname{span}(e)\leq\frac{\Delta\cdot(\log
N)^{128}}{\eta}\cdot\sum_{X\in\tilde{\mathcal{X}}_{1}}|X^{0}|\leq\frac{2(n-|B^{0}|)\cdot\Delta\cdot(\log
N)^{256}}{\eta}.$

Summing up over the three types of clusters, we get that:

$\sum_{e\in
E^{\mathsf{bad}}}\operatorname{span}(e)\leq\frac{4(n-|B^{0}|)\cdot\Delta\cdot
2^{7\sqrt{\log N}}}{\eta}.$ (9)

###  5.2 Part 2: Solving DAG-like SSSP on the Contracted Graph

The second part of our algorithm, we will define a dynamic graph $\hat{H}$
that our algorithm will maintain, which in turn will be used to define an
instance of the DAG-like SSSP problem (see Section 2.4). We will then apply
the algorithm for DAG-like SSSP from Theorem 2.7 to this instance of the
problem. We start by defining the dynamc graph $\hat{H}$, and by providing an
algorithm for maintaining it.

#### Definition of the Dynamic Graph $\hat{H}$

Consider any time $\tau$ during the time horizon ${\mathcal{T}}$, the graph
$H$ and the collection ${\mathcal{X}}$ of clusters at time $\tau$. We say that
a cluster $X\in{\mathcal{X}}$ is _distinguished_ , if it contains some vertex
that currently lies in $B$.

Graph $\hat{H}$ at time $\tau$ is defined as follows. We start with graph $H$,
and, for every cluster $X\in{\mathcal{X}}$ that is not a distinguished
cluster, we contract all vertices in $X$ into a single vertex $v_{X}$ (that we
refer to as a _supernode_). Additionally, all vertices that lie in
distinguished clusters, together with the vertex $t$, are contracted into a
single supernode, that for convenience we continue to denote by $t$. We delete
all loops but keep parallel edges. We also denote the supernode $v_{S}$
corresponding to cluster $S=\left\\{s\right\\}$ by $s$. Consider now any edge
$e$ in the resulting graph. This edge corresponds to some edge in $H$ whose
endpoints lie in different clusters; we do not distinguish between these two
edges. We replace every edge $e=(v_{X},v_{Y})$ in the resulting graph by a
collection $J(e)$ of $O(\log^{2}n)$ parallel edges $(v_{X},v_{Y})$, as
follows. Let $2^{j}$ be the smallest power of $2$ that is greater than
$\operatorname{skip}(e)$. If $e$ is a regular edge in $H$, then set $J(e)$
contains, for all $j\leq j^{\prime}\leq\left\lceil\log n\right\rceil$, a copy
$e_{j^{\prime}}$ of $e$, whose length is $\hat{\ell}(e_{j^{\prime}})=1$, and
weight $w(e_{j^{\prime}})=2^{j^{\prime}}$. Assume now that $e$ is a special
edge of $H$, and denote its length in $H$ by $\ell(e)=2^{i}$. For all $i\leq
i^{\prime}\leq\left\lceil\log\Lambda\right\rceil$ and $j\leq
j^{\prime}\leq\left\lceil\log n\right\rceil$, set $J(e)$ contains a copy
$e_{i^{\prime},j^{\prime}}$ of $e$ with length
$\hat{\ell}(e_{i^{\prime},j^{\prime}})=2^{i^{\prime}}$ and weight
$w(e_{i^{\prime},j^{\prime}})=2^{j^{\prime}}$. This completes the definition
of graph $\hat{H}$.

Consider now some vertex $v\in V(\hat{H})\setminus\left\\{t\right\\}$, and
some integer $0\leq i\leq\left\lceil\log n\right\rceil$. Consider the set of
vertices $U_{i}(v)=\left\\{u\in V(\hat{H})\mid\exists e=(v,u)\in
E(\hat{H})\mbox{ with }w(e)=2^{i}\right\\}$. Notice that set $U_{i}(v)$ may
only contain the nodes $s,t$, and all nodes $v_{Y}\in V(\hat{H})$, such that
some edge $e$ of $H$ connects a vertex of $X$ to a vertex of $Y$, and has
value $\operatorname{skip}(e)\leq 2^{i}$. In the latter case, the distance
between intervals $I_{X}$ and $I_{Y}$ in the $\mathcal{ATO}$ is at most
$2^{i}$, and so at most $2^{i}$ other intervals of the $\mathcal{ATO}$ may lie
between them. Therefore, it is immediate to verify that $|U_{i}(v)|\leq
2^{i+2}$ always holds, establishing Property S1 from the definition of the
DAG-like SSSP problem. Let $n^{\prime}$ be the total number of vertices that
are ever present in the dynamic graph $\hat{H}$. We bound $n^{\prime}$ in the
following simple observation.

######  Observation 5.14.

$n^{\prime}\leq 2(n-|B^{0}|)+2$.

###### Proof.

Let $B^{*}$ be the set of vertices that lie in $B$ at the end of the
algorithm. Clearly, $n^{\prime}\leq n-|B^{*}|+2$. On the other hand, since the
algorithm consists of $\Delta\leq n-|B^{0}|$ iterations, and in every
iteration at most one vertex is deleted from $B$, we get that
$|B^{*}|\geq|B^{0}|-\Delta\geq 2|B^{0}|-n$. Therefore, $n^{\prime}\leq
n-|B^{*}|+2\leq 2(n-|B^{0}|)+2$.

#### Maintaining the Graph $\hat{H}$

At the beginning of the algorithm, we construct the initial graph $\hat{H}$
from graph $H$ as described above. It is easy to verify that this can be done
in time $O(|E(H)|\cdot\log^{2}n)\leq O(n(n-|B^{0}|)\log^{2}n)$.

Next, we show an algorithm that maintains the graph $\hat{H}$, as graph $H$
and the collection ${\mathcal{X}}$ of clusters evolve over time. We will
ensure that the only updates that $\hat{H}$ undergoes are edge deletions and
vertex splitting, as is required from the input to the DAG-like SSSP problem.

Recall that the only updates that graph $H$ undergoes are (i) doubling of the
lengths of its edges; and (ii) deletion of edges incident to $s$ and $t$.
Additionally, some vertices may be deleted from set $B$.

If an edge $e$ that is incident to $s$ or $t$ is deleted from $H$, then we
delete all copies of $e$ from $\hat{H}$. If the length of some edge $e$ is
doubled, and the initial length of edge $e$ was $2^{i}$, then we delete all
copies of $e$ whose length is $2^{i}$ from graph $\hat{H}$.

Assume now that some vertex $v$ is deleted from set $B$. Let
$X\in{\mathcal{X}}$ be the cluster that contains $v$. If $X$ remains a
distinguished cluster, then no additional updates to graph $\hat{H}$ are
required. Otherwise, we perform a _vertex splitting_ operation, that we apply
to supernode $t$, to construct a new supernode $v_{X}$. The corresponding
collection $E^{\prime}$ of edges is defined as follows. Let $e=(a,b)$ be an
edge of $H$, with exactly one endpoint in $X$; assume w.l.o.g. that $a\in X$
and $b\in Y$, where $Y\in{\mathcal{X}}$ is some cluster. Let $2^{j}$ be the
smallest power of $2$ that is greater than $\operatorname{skip}(e)$. Assume
first that $e$ is a regular edge in $H$. Notice that, if $Y$ is not a
distinguished cluster, then, for all $j\leq j^{\prime}\leq\left\lceil\log
n\right\rceil$, graph $\hat{H}$ already contains an edge $(t,v_{Y})$, that is
a copy of $e$, whose length is $1$, and weight is $2^{j^{\prime}}$. We add to
$E^{\prime}$ a copy $(v_{X},v_{Y})$ of $e$, whose length is $1$, and weight is
$2^{j^{\prime}}$. Once the vertex splitting operation is completed, we will
delete from $\hat{H}$ all copies of $e$ that are incident to $t$. If $Y$ is a
distinguished cluster, then, for all $j\leq j^{\prime}\leq\left\lceil\log
n\right\rceil$, we insert a copy $(v_{X},t)$ of the edge $e$ into
$E^{\prime}$, whose length is $1$ and weight is $2^{j^{\prime}}$. Assume now
that $e$ is a special edge of $H$, and denote its length in $H$ by
$\ell(e)=2^{i}$. Consider a pair $i\leq i^{\prime}\leq\left\lceil\log
n\right\rceil$ and $j\leq j^{\prime}\leq\left\lceil\log n\right\rceil$ of
indices. As before, if $Y$ is not a distinguished cluster, then graph
$\hat{H}$ already contains an edge $(t,v_{Y})$, that is a copy of $e$, whose
length is $2^{i^{\prime}}$, and weight is $2^{j^{\prime}}$. We add to
$E^{\prime}$ a copy $(v_{X},v_{Y})$ of $e$, whose length is $2^{i^{\prime}}$,
and weight is $2^{j^{\prime}}$. Once the vertex splitting operation is
completed, we will delete from $\hat{H}$ all copies of $e$ that are incident
to $t$. If $Y$ is a distinguished cluster, then we insert a copy $(v_{X},t)$
of the edge $e$ into $E^{\prime}$, whose length is $2^{i^{\prime}}$ and weight
is $2^{j^{\prime}}$. The case where $b\in X$ and $a\not\in X$ is treated
similarly.

Lastly, it remains to consider updates to the clusters in ${\mathcal{X}}$. All
such updates can be implemented by the following two operations: (i) given a
cluster $X\in{\mathcal{X}}$, and a subset $X^{\prime}\subseteq X$ of vertices,
insert $X^{\prime}$ into ${\mathcal{X}}$ (we call this update _cluster
splitting_); and (ii) given a cluster $X\in{\mathcal{X}}$ and a vertex $x\in
X$, delete $x$ from $X$ (we call this update _vertex deletion_).

Consider first a cluster splitting operation, that is applied to cluster
$X\in{\mathcal{X}}$, through which a new cluster $X^{\prime}\subseteq X$ is
inserted into ${\mathcal{X}}$. Assume first that $X$ is not a distinguished
cluster. We apply a vertex splitting operation to supernode $v_{X}$, inserting
a new supernode $v_{X^{\prime}}$ into $\hat{H}$. The corresponding set
$E^{\prime}$ of edges is defined as follows. Let $e=(a,b)$ be an edge of $H$,
with exactly one endpoint in $X^{\prime}$; assume w.l.o.g. that $a\in
X^{\prime}$ and $b\in Y$, where $Y\in{\mathcal{X}}$ is some cluster. Let
$2^{j}$ be the smallest power of $2$ that is greater than
$\operatorname{skip}(e)$. Assume first that $e$ is a regular edge in $H$.
Notice that, if $Y\neq X$, then, for all $j\leq j^{\prime}\leq\left\lceil\log
n\right\rceil$, graph $\hat{H}$ already contains an edge $(v_{X},v_{Y})$, that
is a copy of $e$, whose length is $1$, and weight is $2^{j^{\prime}}$. We add
to $E^{\prime}$ a copy $(v_{X^{\prime}},v_{Y})$ of $e$, whose length is $1$,
and weight is $2^{j^{\prime}}$. If $Y=X$, then, for all $j\leq
j^{\prime}\leq\left\lceil\log n\right\rceil$, we insert a copy
$(v_{X^{\prime}},v_{X})$ of the edge $e$ into $E^{\prime}$, whose length is
$1$ and weight is $2^{j^{\prime}}$. Assume now that $e$ is a special edge of
$H$, and denote its length in $H$ by $\ell(e)=2^{i}$. Consider a pair $i\leq
i^{\prime}\leq\left\lceil\log n\right\rceil$ and $j\leq
j^{\prime}\leq\left\lceil\log n\right\rceil$ of indices. As before, if $Y\neq
X$, then graph $\hat{H}$ already contains an edge $(v_{X},v_{Y})$, that is a
copy of $e$, whose length is $2^{i^{\prime}}$, and weight is $2^{j^{\prime}}$.
We add to $E^{\prime}$ a copy $(v_{X^{\prime}},v_{Y})$ of $e$, whose length is
$2^{i^{\prime}}$, and weight is $2^{j^{\prime}}$. If $Y=X$, then we insert a
copy $(v_{X^{\prime}},v_{X})$ of the edge $e$ into $E^{\prime}$, whose length
is $2^{i^{\prime}}$ and weight is $2^{j^{\prime}}$. The case where $b\in
X^{\prime}$ and $a\not\in X^{\prime}$ is treated similarly.

If $X^{\prime}$ is a distinguished cluster, then so is $X$, and no updates to
$\hat{H}$ are required. If $X$ is a distinguished cluster but $X^{\prime}$ is
not a distinguished cluster, then the update procedure to graph $\hat{H}$ is
almost identical to that when a distinguished cluster becomes a non-
distinguished cluster. Specifically, we apply a vertex-splitting operation to
$t$, following which a supernode $v_{X^{\prime}}$ representing the cluster
$X^{\prime}$ is inserted into $\hat{H}$. The remaining details a
straightforward and are omitted here.

Lastly, assume that a vertex $x$ is deleted from some cluster
$X\in{\mathcal{X}}$. In this case, we consider every edge $e\in E(H)$ that is
incident to $x$ one by one. Let $y$ denote the other endpoint of $e$. If $X$
is not a distinguished cluster, then we delete every copy of $e$ that is
incident to $v_{X}$ from $\hat{H}$. Otherwise, we delete every copy of $e$
that is incident to $t$ from $\hat{H}$.

To summarize, we view a cluster-splitting operation that is applied to a
cluster $X$ as consisting of two steps. In the first step, a new cluster
$X^{\prime}\subseteq X$ is inserted into ${\mathcal{X}}$, and in the second
step, the vertices of $X^{\prime}$ are deleted from $X$. Recall that,
following such cluster-splitting updates, it is possible that for some edge
$e\in E(H)$ whose endpoints lie in different clusters, the value
$\operatorname{skip}(e)$ increases. In such a case, we delete from $\hat{H}$
all copies of $e$, whose weight is below the new value
$\operatorname{skip}(e)$. This concludes the description of the algorithm for
maintaining the graph $\hat{H}$.

It is easy to verify that the total time that is required in order to compute
and maintain graph $\hat{H}$ is asymptotically bounded by the total time
required to maintain graph $H$ and the collection ${\mathcal{X}}$ of clusters
times $O(\log^{6}n)$. Indeed, from 5.11, every cluster in
$\tilde{\mathcal{X}}^{\prime}_{2}$ has $O(\log n)$ close descendants, and so
it may have at most $O(\log^{2}n)$ descendant clusters overall. Therefore,
every vertex of $H$ may belong to $O(\log^{2}n)$ clusters over the course of
the algorithm. For each edge $e=(x,y)$, for every pair $X,X^{\prime}$ of
clusters that contain $x$ and $y$ respectively, at any time during the
algorithm, $O(\log^{2}n)$ copies of $e$ connecting the supernodes
corresponding to $X$ and $X^{\prime}$ may be present in $\hat{H}$. Overall, at
most $O(\log^{5}n)$ copies of an edge of $H$ may ever be present in $\hat{H}$,
and so the total time that is required in order to compute and maintain graph
$\hat{H}$ is asymptotically bounded by the total time required to maintain
graph $H$ and the collection ${\mathcal{X}}$ of clusters times $O(\log^{6}n)$.

#### Solving the DAG-like SSSP Problem on $\hat{H}$

So far we have defined a dynamic graph $\hat{H}$ with lengths and weights on
edges and two special edges $s$ and $t$, that undergoes an online sequence of
edge-deletion and vertex-splitting updates, such that Property S1 holds. We
consider an instance of the DAG-like SSSP problem defined on graph $\hat{H}$
with parameter $\Gamma=64n\cdot 2^{8\sqrt{\log N}}$, parameter $d$ replaced by
$\frac{\Lambda}{4}$, and $\epsilon=\frac{1}{10}$. We apply the algorithm from
Theorem 2.7 to the resulting instance of the DAG-like SSSP problem. Recall
that the total update time of this algorithm is bounded by:

$\tilde{O}\left((n^{\prime})^{2}+|E(\hat{H})|+\Gamma\cdot
n^{\prime}\right)\leq\tilde{O}\left(n\cdot(n-|B^{0}|)\cdot 2^{8\sqrt{\log
N}}\right)$

Overall, the total time that is required for Part 1 of the algorithm, and also
for maintaining graph $\hat{H}$ and for maintaining the data structures for
the DAG-like SSSP problem from Theorem 2.7 is bounded by:

$c_{1}\cdot n\cdot(n-|B^{0}|)\cdot 2^{c_{2}\sqrt{\log N}}\cdot(\log
N)^{16c_{2}r+2c_{2}}.$

#### Computing the Cut-Witness

Once the algorithm for the DAG-like SSSP problem terminates, we are guaranteed
that graph $\hat{H}$ contains no $s$-$t$ path $Q$ with $\sum_{e\in
E(Q)}\hat{\ell}(e)\leq\frac{\Lambda}{4}$ and $\sum_{e\in E(Q)}w(e)\leq\Gamma$.