# Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial
Algorithm

Julia Chuzhoy Toyota Technological Institute at Chicago. Email:
<EMAIL_ADDRESS>Supported in part by NSF grant CCF-2006464 and NSF HDR
TRIPODS award 2216899. Sanjeev Khanna University of Pennsylvania,
Philadelphia, PA. Email<EMAIL_ADDRESS>Supported in part by NSF
awards CCF-1934876 and CCF-2008305.

Maximum bipartite matching (MBM) is a fundamental problem in combinatorial
optimization with a long and rich history. A classic result of Hopcroft and
Karp [HK73] provides an $O(m\sqrt{n})$-time algorithm for the problem, where
$n$ and $m$ are the number of vertices and edges in the input graph,
respectively. For dense graphs, an approach based on fast matrix
multiplication achieves a running time of $O(n^{2.371})$ [IM81, MS04]. For
several decades, these results represented state-of-the-art algorithms, until,
in 2013, Madry introduced a powerful new approach for solving MBM using
continuous optimization techniques. This line of research, that builds on
continuous techniques based on interior-point methods, led to several
spectacular results, culminating in a breakthrough $m^{1+o(1)}$-time algorithm
for min-cost flow, that implies an $m^{1+o(1)}$-time algorithm for MBM as
well.

These striking advances naturally raise the question of whether combinatorial
algorithms can match the performance of the algorithms that are based on
continuous techniques for MBM. One reason to explore combinatorial algorithms
is that they are often more transparent than their continuous counterparts,
and that the tools and techniques developed for such algorithms may be useful
in other settings, including, for example, developing faster algorithms for
maximum matching in general graphs. A recent work of Chuzhoy and Khanna [CK24]
made progress on this question by giving a combinatorial
$\tilde{O}(m^{1/3}n^{5/3})$-time algorithm for MBM, thus outperforming both
the Hopcroft-Karp algorithm and matrix multiplication based approaches, on
sufficiently dense graphs. Still, a large gap remains between the running time
of their algorithm and the almost linear-time achievable by algorithms based
on continuous techniques. In this work, we take another step towards narrowing
this gap, and present a randomized $n^{2+o(1)}$-time combinatorial algorithm
for MBM. Thus in dense graphs, our algorithm essentially matches the
performance of algorithms that are based on continuous methods.

Similar to the classical algorithms for MBM and the approach of [CK24], our
algorithm is based on iterative augmentation of a current matching using
augmenting paths in the corresponding (directed) residual flow network. Our
main contribution is a recursive algorithm that exploits the special structure
of the resulting flow problem to recover an $\Omega(1/\log^{2}n)$-fraction of
the remaining augmentations in $n^{2+o(1)}$ time.

Finally, we obtain a randomized $n^{2+o(1)}$-time algorithm for maximum
vertex-capacitated $s$-$t$ flow in directed graphs when all vertex capacities
are identical, using a standard reduction from this problem to MBM.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Techniques
    2. 1.2 Organization
  2. 2 Preliminaries
    1. 2.1 Even-Shiloach Tree for Weighted Directed Graphs
    2. 2.2 The Adjacency-List Representation of Graphs
    3. 2.3 Overview of the $\mathcal{ATO}$ framework
    4. 2.4 SSSP in DAG-like Graphs
  3. 3 High-Level Overview of the Algorithm
    1. 3.1 Well-Structured Graphs and Well-Structured Cuts
    2. 3.2 The RouteAndCut problem
    3. 3.3 Completing the Proof of Theorem 1.1
    4. 3.4 Proof of Theorem 3.6 – High Level Overview
      1. 3.4.1 An Auxiliary Graph $G^{\prime}$ and its Properties
    5. 3.5 Solving $r$-Restricted $\mathsf{RouteAndCut}$ via the Modified MWU Framework and a Reduction to $r$-Restricted $s$-$t$-SP
      1. 3.5.1 The Modified MWU Framework
      2. 3.5.2 The $r$-Restricted $s$-$t$-SP Problem
      3. 3.5.3 A Simple Algorithm for $s$-$t$-SP
  4. 4 Tools for Expander-Like Graphs and the $\mathsf{MaintainCluster}$ Problem
    1. 4.1 A Subdivided Graph and a New Definition of Cut Sparsity
    2. 4.2 The $\mathsf{MaintainCluster}$ Problem
    3. 4.3 The $\mathsf{MaintainSpecialCluster}$ Problem
    4. 4.4 Completing the Proofs of Theorem 3.9 and Theorem 4.10
  5. 5 From $r$-Restricted $\mathsf{MaintainCluster}$ and $\mathsf{MaintainSpecialCluster}$ to $(r+1)$-Restricted $\mathsf{RouteAndCut}$: Proof of Theorem 4.11
    1. 5.1 Part 1 - Maintaining the $\mathcal{ATO}$
      1. 5.1.1 Leaf Clusters
      2. 5.1.2 Non-Leaf Regular Clusters
      3. 5.1.3 The Special Cluster
      4. 5.1.4 Child Clusters, Descendant Clusters, and a Useful Bound
      5. 5.1.5 Bounding the Running Time of Part 1 and Probability of Failure
      6. 5.1.6 Bounding the Total Span of Bad Edges
    2. 5.2 Part 2: Solving DAG-like SSSP on the Contracted Graph
    3. 5.3 Completing the Algorithm
  6. 6 Layered Connectivity Data Structure and an Algorithm for the $\mathsf{MaintainSpecialCluster}$ problem
    1. 6.1 The Layered Connectivity Data Structure
    2. 6.2 Procedure $\mathsf{ReconnectLayer}$
      1. 6.2.1 Modified Graph $H^{\prime}$.
      2. 6.2.2 Parameters for the $\mathsf{RouteAndCut}$ Problem Instances
      3. 6.2.3 Description of an Iteration
      4. 6.2.4 Constructing a New Layered Connectivity Data Structure.
      5. 6.2.5 Analysis of the Running Time
      6. 6.2.6 Special Case: $k<2^{20}\cdot d^{\prime}\cdot\log^{6}N$.
    3. 6.3 $\mathsf{ConnectToCenters}$ Problem
    4. 6.4 An Algorithm for the $\mathsf{ConnectToCenters}$ Problem
      1. 6.4.1 The Data Structures
      2. 6.4.2 The Algorithm
      3. 6.4.3 Procedure $\mathsf{ProcessCut}$
      4. 6.4.4 Bounding $|M|$ and the Running Time of the Algorithm
      5. 6.4.5 Maintaining the Additional Data Structures
    5. 6.5 An Algorithm for the $\mathsf{MaintainSpecialCluster}$ Problem
  7. 7 From the $\mathsf{MaintainCluster}$ Problem to $\mathsf{RouteAndCut}$ Problem – Comleting the Proof of Theorem 4.12
    1. 7.1 Partition into Phases and Probability of Failure
    2. 7.2 Preprocessing Step: Subsampling
      1. 7.2.1 Bad Event ${\cal{E}}_{1}$
      2. 7.2.2 Well-Structured Cuts and Their Structure
      3. 7.2.3 Bad Event ${\cal{E}}_{2}$
      4. 7.2.4 Bad Event ${\cal{E}}_{3}$
      5. 7.2.5 Bad Event ${\cal{E}}_{4}$
    3. 7.3 Finalizing Cuts
    4. 7.4 First Data Structure: Expander $X$ and its Embedding
      1. 7.4.1 Initialization
      2. 7.4.2 Maintaining the Expander
    5. 7.5 Second Data Structure: Connecting to the Vertices of $X$
    6. 7.6 Additional Data Structures
    7. 7.7 The Remainder of the Algorithm
      1. 7.7.1 Responding to Queries
      2. 7.7.2 Post-Query Updates
      3. 7.7.3 The Cleanup Procedure
      4. 7.7.4 Procedure $\mathsf{ProcessCut}^{\prime}$
      5. 7.7.5 Maintaining the Additional Data Structures and the Final Accounting
  8. A Proofs Omitted from Section 4
    1. A.1 Proof of 4.4
    2. A.2 Proof of 4.5
  9. B Proofs Omitted from Section 5
    1. B.1 Proof of 5.5
    2. B.2 Proof of 5.6
    3. B.3 Proof of 5.7
    4. B.4 Proof of 5.8
    5. B.5 Proof of 5.10
    6. B.6 Proof of 5.11
  10. C Proofs Omitted from Section 6
    1. C.1 Proof of 6.2
    2. C.2 Proof of 6.4
    3. C.3 Proof of 6.12
    4. C.4 Proof of Corollary 6.13
    5. C.5 Proof of 6.14
  11. D Proofs Omitted from Section 7
    1. D.1 Proof of 7.2
    2. D.2 Proof of 7.9
    3. D.3 Proof of 7.14
    4. D.4 Proof of 7.15
    5. D.5 Proof of 7.21

##  1 Introduction

We consider the classical Maximum Bipartite Matching problem, where the goal
is to compute a maximum-size matching in the given input bipartite graph $G$.
Throughout, we denote the number of vertices and the number of edges in $G$ by
$n$ and $m$, respectively. Maximum Bipartite Matching is one of the most
central and extensively studied problems in computer science and related
disciplines, with connections to many other fundamental graph optimization
problems.

It is well known that Maximum Bipartite Matching can be reduced to computing a
maximum $s$-$t$ flow in a directed flow network with unit edge capacities. The
Ford-Fulkerson algorithm [FF56] for maximum $s$-$t$ flow then immediately
implies an $O(mn)$-time algorithm for Maximum Bipartite Matching. The
algorithm is conceptually simple, and maintains a matching $M$, starting with
$M=\emptyset$. As long as $M$ is not optimal, we can augment it by computing
an $s$-$t$ path in the resulting residual flow network. A celebrated work of
Hopcroft and Karp [HK73] provides a significantly more efficient
$O(m\sqrt{n})$-time implementation of this idea by iteratively computing a
maximal collection of internally disjoint augmenting $s$-$t$ paths of shortest
possible length in the residual flow network. This result remained the fastest
known algorithm for several decades, except for the special case of very dense
graphs, where fast matrix multiplication techniques were shown to yield an
$O(n^{\omega})$-time algorithm [IM81, MS04]. Starting in 2008, a new paradigm
emerged, namely, the use of continuous techniques as a method for obtaining
fast algorithms for various flow problems, that ultimately revolutionized the
field. As a first illustration of this paradigm, the work of Daitch and
Spielman [DS08], building on the breakthrough result of Spielman and Teng
[ST04] for efficiently solving Laplacian systems, gave an
$\widetilde{O}(m^{3/2})$-time algorithm for directed maximum $s$-$t$ flow.
Later, Madry [Mad13] used this paradigm to design an algorithm for directed
maximum $s$-$t$ flow with $\tilde{O}(m^{10/7})$ running time, obtaining the
first substantial improvement over the algorithm of Hopcroft and Karp for
Maximum Bipartite Matching in sparse graphs. A sequence of remarkable
developments [Mad16, LS19, CMSV17, LS20, AMV20, vdBLN+20] recently culminated
in a deterministic $m^{1+o(1)}$-time algorithm for directed maximum $s$-$t$
flow [CKL+22, vdBCK+23], thereby providing an almost linear-time algorithm for
Maximum Bipartite Matching. In all these recent algorithms, the directed flow
problem is cast as a linear program, which is then solved via interior-point
methods (IPM). In every iteration of the IPM, one needs to either solve a
Laplacian system, or another efficiently solvable problem on undirected
graphs, such as min-ratio cycle in [CKL+22]. This approach is further combined
with dynamic graph data structures to make it even more efficient.

In view of this recent history, it is natural to ask whether combinatorial
techniques can be used to design algorithms for Maximum Bipartite Matching
(and also other flow-like problems), whose performance matches that of
algorithms that are based on continuous methods. There are several reasons to
focus on combinatorial techniques. First, they tend to be more transparent
than their continuous counterparts. Second, it is likely that tools and
techniques that are developed in order to design a combinatorial algorithm for
as fundamental a problem as Maximum Bipartite Matching will prove useful in
other applications. Lastly, while continuous techniques led to an
$m^{1+o(1)}$-time algorithm for Maximum Bipartite Matching, the landscape of
fast algorithms for the Maximum Matching problem in general graphs did not
benefit from these developments. In dense graphs, a fast-matrix multiplication
based approach gives $O(n^{2.371})$-time algorithm for Maximum Matching in
general graphs [IM81, MS04]. More interestingly, in sparse to moderately dense
graphs, the best known runtime still stands on $\tilde{O}(m\sqrt{n})$ [MV80,
Vaz94, GK04, Gab17] and utilizes an augmenting-paths based approach, similar
to that used in combinatorial algorithms for Maximum Bipartite Matching.

In a very recent work, Chuzhoy and Khanna [CK24] made progress on narrowing
the striking gap between the performance of combinatorial and IPM-based
approaches for Maximum Bipartite Matching, by providing a combinatorial
deterministic $\tilde{O}(m^{1/3}n^{5/3})$-time algorithm, thus outperforming
both the Hopcroft-Karp algorithm, and the matrix multiplication based
approaches on sufficiently dense graphs. Still, a large gap remains between
the performance of the best combinatorial algorithms and the almost linear-
time achievable by algorithms based on continuous techniques. In particular,
on dense graphs, the performance gap incurred by the current best
combinatorial algorithm is $\Omega(n^{1/3})$. In this work, we take another
step towards narrowing this performance gap, and essentially eliminate it in
dense graphs. Our main result is summarized in the following theorem.

######  Theorem 1.1.

There is a randomized combinatorial algorithm for the Maximum Bipartite
Matching problem, that, given an $n$-vertex bipartite graph $G$, outputs a
maximum matching $M$ in $G$ with probability at least
$1-1/\operatorname{poly}(n)$. The running time of the algorithm is
$O\left(n^{2}\cdot 2^{O(\sqrt{\log n}\cdot\log\log n)}\right)$.

Our algorithm outperforms the Hopcroft-Karp algorithm on graphs with
$\omega(n^{1.5})$ edges, and in dense graphs, it essentially matches the
performance of algorithms based on continuous techniques. Furthermore, in
almost all edge density regimes, this algorithm outperforms the runtime
achieved in [CK24].

Using a standard reduction from vertex-capacitated flow in directed graphs to
Maximum Bipartite Matching (see Theorem 16.12 in [Sch03], for instance), we
also obtain a combinatorial algorithm with similar running time for maximum
vertex-capacitated flow when all vertex capacities are identical.

######  Corollary 1.2.

There is a randomized combinatorial algorithm for the directed maximum $s$-$t$
flow problem with uniform vertex capacities, that given an $n$-vertex directed
graph $G$, outputs a maximum $s$-$t$ flow with probability at least
$1-1/\operatorname{poly}(n)$. The running time of the algorithm is
$O\left(n^{2}\cdot 2^{O(\sqrt{\log n}\cdot\log\log n)}\right)$.

Similarly to the classical algorithms for Maximum Bipartite Matching, our
approach for proving Theorem 1.1 is based on iteratively augmenting a current
matching using augmenting paths in the residual flow network. We employ the
multiplicative weights update (MWU) framework, that effectively reduces the
underlying flow problem to decremental single-source shortest paths (SSSP) in
directed graphs, a connection first observed by Madry [Mad10] and also used in
[CK24]. As observed in [CK24], this reduction results in a special case of
decremental SSSP that appears significantly easier than general decremental
directed SSSP. Our main contribution is a recursive algorithm that exploits
the special structure of the resulting flow problem to recover an
$\Omega(1/\log^{2}n)$-fraction of the remaining augmentations in $n^{2+o(1)}$
time. We abstract this task as a problem called $\mathsf{RouteAndCut}$, where
the input is a directed graph $G$, two disjoint sets $A,B$ of its vertices
with $|A|\leq|B|$, and two additional parameters $1\leq\eta\leq\Delta$. The
goal is to either compute a collection ${\mathcal{P}}$ of at least
$\Omega(\Delta/\operatorname{poly}\log n)$ paths that connects distinct
vertices of $A$ to distinct vertices of $B$ with vertex-congestion at most
$\eta$; or to output a cut that approximately certifies infeasibility of the
desired routing. Our main result is a randomized algorithm for
$\mathsf{RouteAndCut}$, whose running time is bounded by
$n^{1+o(1)}\cdot(n-|B|)$. It is worth highlighting that when $|B|$ is
sufficiently large, this running time may be much smaller than $|E(G)|$. This
performance gain for large sets $B$ serves as a crucial building block for our
$n^{2+o(1)}$-time algorithm.

As in the work of [CK24], the task of efficiently solving
$\mathsf{RouteAndCut}$ in turn relies on an efficient algorithm for
maintaining an expander in a dynamically changing graph, a problem that we
refer to as $\mathsf{MaintainCluster}$. One key contribution of our work is
the introduction of a parameterized version of both these problems that allows
us to use a bootstrapping approach in the design of our algorithm, where we
exploit efficient algorithms for one problem to obtain efficient algorithms
for the other problem and vice versa. Another key technical contribution is an
efficient algorithm for a new problem that we introduce, called
$\mathsf{ConnectToCenters}$, that plays a central role in efficiently
maintaining short paths from all vertices of a given graph $G$ to a pre-
specified collection of “center” vertices, even as $G$ undergoes online
updates. This problem may be viewed as a representative abstraction of a
common paradigm used in many graph algorithms, in which an expander is
embedded into the input graph, and all graph vertices are then routed to the
vertices of the expander. As such, our algorithm for this problem may prove
useful in other applications. Finally, another insight utilized by our
algorithm is an explicit recognition of the fact that each iteration of the
MWU algorithm leads to very specific kind of updates in the underlying SSSP
instance, namely, well-behaved increases in the lengths of some edges. While
these length increases can easily be simulated as edge deletions, a black-box
simulation as an instance of decremental SSSP gives away some of the inherent
algorithmic advantages offered by these special kind of updates that our
algorithm exploits. We give a detailed overview of our algorithm and its
comparison to the algorithm of [CK24] in the next subsection.

We conclude by noting that in addition to the conceptual simplicity of a
combinatorial augmenting path based approach to solve Maximum Bipartite
Matching, the techniques developed here for speeding up augmentations may also
prove useful in obtaining faster algorithms for Maximum Matching in general
graphs. We also believe that some of the technical tools that we introduce,
such as an efficient algorithm for the $\mathsf{ConnectToCenters}$ problem
that we describe in more detail below, are of independent interest.

###  1.1 Our Techniques

Our algorithm builds on and extends the techniques of [CK24], which, in turn,
build on the algorithm of [BGS20] for the directed decremental Single-Source
Shortest Path (SSSP) problem. We start with a high-level overview of the
algorithm of [CK24], and then provide the description of our improved
algorithm.

It is well known that the Maximum Bipartite Matching problem in a graph $G$
can be equivalently cast as the problem of computing an integral maximum
$s$-$t$ flow in a corresponding directed flow network $G^{\prime}$ with unit
edge capacities. We can view any given matching $M$ in $G$ as defining an
$s$-$t$ flow $f$ in $G^{\prime}$ of value $|M|$. We let $H=G^{\prime}_{f}$ be
the corresponding residual flow network, that we refer to as the _residual
flow network corresponding to matching $M$_. We note that the residual flow
network $H$ has a special structure: namely, each vertex in $H$ has in-degree
$1$ or out-degree $1$. Therefore, if ${\mathcal{P}}$ is a collection of paths
in $H$ causing edge-congestion at most $\eta$, then the paths in
${\mathcal{P}}$ cause vertex-congestion at most $\eta$ and vice versa. For all
problems that we define below, we assume that their input graph also has this
special structure. For convenience, we will focus on edge-congestion, and on
edge-based cuts in such graphs. We also note that any directed graph can be
converted into a graph with this special structure by replacing every vertex
$v$ with a pair $v^{+},v^{-}$ of new vertices, such that all edges that enter
$v$ become incident to $v^{-}$, and all edges leaving $v$ become incident to
$v^{+}$, and inserting the edge $(v^{-},v^{+})$ into the graph.

The residual network $H$ corresponding to a matching $M$ contains
$\Delta=\mathsf{OPT}-|M|$ edge-disjoint $s$-$t$ paths, where $\mathsf{OPT}$ is
the value of the maximum bipartite matching. Suppose now that we can design an
algorithm that computes a collection ${\mathcal{P}}$ of
$\Omega(\Delta/\operatorname{poly}\log n)$ $s$-$t$ paths in $H$, that cause
$O(\operatorname{poly}\log n)$ edge-congestion. Using standard methods, we can
then efficiently recover a collection ${\mathcal{P}}^{\prime}$ of
$\Omega(\Delta/\operatorname{poly}\log n)$ edge-disjoint $s$-$t$ paths in $H$,
which can in turn be used in order to augment the current matching $M$,
thereby obtaining a new matching $M^{\prime}$ of cardinality
$|M|+\Omega(\Delta/\operatorname{poly}\log n)$. In other words,
$\mathsf{OPT}-|M^{\prime}|\leq(\mathsf{OPT}-|M|)\cdot(1-1/\operatorname{poly}\log
n)$, so the gap between the optimal solution value and the size of the
matching the algorithm maintains reduces by at least factor
$(1-1/\operatorname{poly}\log n)$. It is then easy to verify that, after
$O(\operatorname{poly}\log n)$ such iterations, the algorithm obtains an
optimal matching. This is precisely the high-level approach that was used by
[CK24], and we follow it in this work as well. In order to obtain an algorithm
for Maximum Bipartite Matching, it is now sufficient to design a procedure
that, given a residual flow network $H$ corresponding to the current matching
$M$, efficiently computes the set ${\mathcal{P}}$ of $s$-$t$ paths in $H$ with
the above properties.

For technical reasons that will become clear later, we define a slightly more
general problem, that we call $\mathsf{RouteAndCut}$. In this problem, the
input is a directed graph $H$, two disjoint sets $A,B$ of its vertices with
$|A|\leq|B|$, and two parameters $1\leq\Delta\leq\min\left\\{|A|,|B|\right\\}$
and $1\leq\eta\leq\Delta$. The goal is to either compute a collection
${\mathcal{Q}}$ of $\Omega(\Delta/\operatorname{poly}\log n)$ paths, each of
which connects a distinct vertex of $A$ to a distinct vertex of $B$, such that
the paths in ${\mathcal{Q}}$ cause congestion $\tilde{O}(\eta)$; or to compute
a cut $(X,Y)$ in $H$ with $|E_{H}(X,Y)|\ll\Delta/\eta$, with $X$ containing a
large fraction of vertices of $A$, and $Y$ containing a large fraction of the
vertices of $B$. While [CK24] do not explicitly define and solve this problem,
their algorithm can be adapted to solve a special case of
$\mathsf{RouteAndCut}$, where $\eta\leq O(\operatorname{poly}\log n)$. So for
brevity, we will say that the algorithm of [CK24] solves this special case of
$\mathsf{RouteAndCut}$. Clearly, an algorithm for the $\mathsf{RouteAndCut}$
problem can be used in order to compute a collection ${\mathcal{P}}$ of paths
in the residual flow network $H$ corresponding to the current matching $M$,
with the desired properties that we described above.

The $\mathsf{RouteAndCut}$ problem falls into the broader and the extensively
studied class of graph routing and flow problems. One standard approach for
obtaining fast algorithms for such problems, due to [GK98, Fle00, AAP93], is
via the Multiplicative Weight Update (MWU) method. It was further observed by
Madry [Mad10] that this approach can be viewed as reducing a given flow
problem to a variant of decremental SSSP or APSP. In our case, the reduction
is to decremental SSSP in directed graphs. While strong lower bounds are known
for exact algorithms for decremental SSSP and APSP (see, e.g. [DHZ00, RZ11,
HKNS15, ABKZ22, ABF23]), we can exploit the special properties of the SSSP
instances that arise from the $\mathsf{RouteAndCut}$ problem in order to
obtain faster algorithms, an approach that was also used by [CK24].

We note that [BGWN20] provided a $(1+\epsilon)$-approximation algorithm for
directed decremental SSSP with total update time
$\widetilde{O}(n^{2}/\epsilon)$, assuming all edge lengths are poly-bounded.
Unfortunately, their algorithm can only withstand an _oblivious adversary_ ;
in other words, the sequence of edge-deletions from the input graph $G$ must
be fixed in advance and may not depend on the algorithm’s responses to
queries. Instances of decremental SSSP arising from the MWU framework
crucially require algorithms that can withstand an _adaptive adversary_ ,
where the choice of the edge to be deleted in every update may depend on the
algorithm’s past behavior. A recent work of [BGS20] provided a
$(1+\epsilon)$-approximation algorithm for the directed decremental SSSP
problem with an adaptive adversary, that achieves total update time
$O\left(\frac{n^{8/3+o(1)}}{\epsilon}\right)$ (assuming that all edge lengths
are poly-bounded). While this total update time is too high for speeding up
algorithms for Maximum Bipartite Matching, their approach was adapted by
[CK24] to handle the specific instances of SSSP that they obtain, leading to
faster algorithms for Maximum Bipartite Matching. Specifically, one of the key
observations of [CK24] is that the SSSP instances that arise from applying the
MWU method to the Maximum Bipartite Matching problem have the property that
all queries are between a fixed pair $(s,t)$ of vertices, and a rather large
approximation factor is acceptable. Moreover, by slightly modifying the
standard MWU framework, they ensure that it is sufficient that the algorithm
for the SSSP problem only responds to shortest-path queries as long as the
current graph $H$ contains a collection of least
$\Omega(\Delta/\operatorname{poly}\log n)$ disjoint and short $s$-$t$ paths,
where $\Delta$ is the target number of augmenting paths that the algorithm
aims to produce. We also follow their approach, and reduce the
$\mathsf{RouteAndCut}$ problem, via a slightly modified MWU method, to a
special case of directed decremental SSSP, that we refer to as decremental
$s$-$t$-SP, that has all of the above properties. We note that $s$-$t$-SP is
somewhat more general than the special case of the SSSP problem that was
considered in [CK24], since they only provide an algorithm for the special
case of $\mathsf{RouteAndCut}$ where $\eta\leq O(\operatorname{poly}\log n)$,
while we need an algorithm that works for a wider range of values of parameter
$\eta$. For now we focus on the description of their algorithm, and we assume
for simplicity that $\eta=1$ in this discussion.

The algorithm of [CK24] for a special case of the decremental $s$-$t$-SP
problem follows the high-level approach of [BGS20], that consists of two
parts. First, they maintain a partition ${\mathcal{X}}$ of graph
$H\setminus\left\\{s,t\right\\}$ into a collection of _expander-like graphs_ ;
we abstract the problem of maintaining each such graph, that we call
$\mathsf{MaintainCluster}$ problem, below. Intuitively, the
$\mathsf{MaintainCluster}$ subroutine is given as input a vertex-induced
subgraph $H^{\prime}$ of $H$, and a distance parameter $d$, with $H^{\prime}$
undergoing an online sequence of edge deletions. It needs to efficiently
support short-path queries in $H^{\prime}$: given a pair $x,y\in
V(H^{\prime})$ of vertices, return an $x$-$y$ path of length at most $d$ in
$H^{\prime}$. However, it may, at any time, produce a cut $(A,B)$ in
$H^{\prime}$ of sparsity at most $O\left(\frac{\operatorname{poly}\log
n}{d}\right)$, after which the vertices on one side of the cut are deleted
from $H^{\prime}$, and the algorithm needs to continue with the resulting
graph. The second main ingredient in the algorithm of [CK24] is the
Approximate Topological Order ($\mathcal{ATO}$) framework of [BGWN20] (which
is in turn based on the works of [GWN20] and [Ber17]), combined with the
algorithm of [BGWN20] for decremental SSSP on “almost” DAG’s. The latter
algorithm is applied to the graph $\hat{H}$, that is obtained from $H$ by
contracting every almost-expander $X\in{\mathcal{X}}$ into a single vertex. We
now discuss each of these components in turn, starting with the
$\mathcal{ATO}$ framework.

##### The $\mathcal{ATO}$ framework.

The Approximate Topological Order ($\mathcal{ATO}$) framework of
[BGWN20]111According to [BGWN20], while the $\mathcal{ATO}$ technique was
first explicitly defined in [BGWN20], the work of [GWN20] can be viewed as
(implicitly) using this technique. is a central component in the algorithms of
[BGS20, CK24], as well as our algorithm. The framework was first introduced as
the means of reducing the decremental SSSP problem on general directed graphs
to decremental SSSP on “almost DAG’s”.

An $\mathcal{ATO}$ data structure in a dynamic graph $H$ must maintain a
partition ${\mathcal{X}}$ of the vertices of $H$ into subsets. We refer to the
sets $X\in{\mathcal{X}}$ as _clusters_ , and to ${\mathcal{X}}$ as a
_clustering_. The only allowed changes to the clustering ${\mathcal{X}}$ are
_cluster splittings_ : given an existing cluster $X\in{\mathcal{X}}$ and a
subset $X^{\prime}\subseteq X$ of its vertices, delete the vertices of
$X^{\prime}$ from $X$, and add $X^{\prime}$ as a new cluster to
${\mathcal{X}}$. We assume further that the input graph $H$ contains two
special vertices $s$ and $t$, and that clusters $S=\left\\{s\right\\}$ and
$T=\left\\{t\right\\}$ always lie in ${\mathcal{X}}$. In addition to
maintaining the clustering ${\mathcal{X}}$, the $\mathcal{ATO}$ must maintain
an _ordering_ $\sigma$ of its clusters. Assume that
${\mathcal{X}}=\left\\{X_{1},\ldots,X_{r}\right\\}$, and that the clusters are
indexed according to the ordering $\sigma$. Assume further that a cluster
$X_{i}$ undergoes splitting, with the new cluster $X^{\prime}_{i}\subseteq
X_{i}$ inserted into ${\mathcal{X}}$. Then the ordering $\sigma$ must evolve
in a _consistent_ manner, that is, the new ordering must be either
$(X_{1},\ldots,X_{i-1},X^{\prime}_{i},X_{i}\setminus
X^{\prime}_{i},X_{i+1},\ldots,X_{r})$, or
$(X_{1},\ldots,X_{i-1},X_{i}\setminus
X^{\prime}_{i},X^{\prime}_{i},X_{i+1},\ldots,X_{r})$. Consider now some edge
$e=(x,y)$ of $H$, and assume that $x\in X_{i}$ and $y\in X_{j}$. If $X_{i}$
appears before $X_{j}$ in the ordering $\sigma$, then we say that $e$ is a
_left-to-right_ edge; if $i=j$, we say that it is a _neutral_ edge; and
otherwise we say that it is a _right-to-left_ edge. If $e$ is a right-to-left
edge, then we define its _span_ :
$\operatorname{span}(e)=\sum_{i^{\prime}=j}^{i}|X_{i^{\prime}}|$ (we assume
here that the sets in ${\mathcal{X}}$ are indexed according to the ordering
$\sigma$). Let $\hat{H}$ be the contracted graph corresponding to $H$: that
is, $\hat{H}$ is obtained from $H$ by contracting each of the clusters
$X\in{\mathcal{X}}$ into a vertex $v_{X}$. For simplicity, we will refer to
the vertices $v_{S}$ and $v_{T}$ as $s$ and $t$, respectively. Intuitively, if
we could maintain the $\mathcal{ATO}$ without introducing any right-to-left
edges, then the corresponding contracted graph $\hat{H}$ is a DAG, and the
ordering $\sigma$ associated with the $\mathcal{ATO}$ naturally defines a
topological ordering of the vertices of $\hat{H}$. We could then use the
algorithm of [BGWN20] for decremental SSSP in DAG’s, that builds on the work
of [Ber17, GWN20], in order to support approximate shortest path queries in
$\hat{H}$ between $s$ and other vertices of $\hat{H}$, with total update time
$\widetilde{O}(n^{2})$. But in order to be able to support shortest $s$-$t$
path queries in the original graph $H$, we need to ensure that the diameters
of the subgraphs $H[X]$ corresponding to the clusters $X\in{\mathcal{X}}$ are
sufficiently small, and that we can support approximate shortest-path queries
between arbitrary pairs of vertices within each such graph efficiently.

Towards this end, it was observed by [BGWN20] that the algorithm for
decremental SSSP in DAG’s can be further extended to “almost DAG’s”: suppose
$G$ is a directed graph, and let $\rho$ be a fixed ordering of its vertices.
Assume that $V(G)=\left\\{v_{1},\ldots,v_{n}\right\\}$, where the vertices are
indexed according to the ordering $\rho$. If $e=(v_{i},v_{j})$ is an edge with
$i>j$, then we say that $e$ is a _right-to-left_ edge of $G$, and we say that
its _width_ is $i-j$. It was shown in [BGWN20] that the algorithm for
decremental SSSP on DAG’s could be extended to such graphs $G$, provided that
the total width of all right-to-left edges is relatively small. Specifically,
the running time of their algorithm becomes roughly
$\tilde{O}(n^{2}+\Gamma\cdot n)$, where $\Gamma$ is the total width of the
right-to-left edges.

Assume now that the algorithm for SSSP on the almost-DAG graph $G$ only needs
to respond to approximate shortest-path queries between a specific fixed pair
$s,t$ of vertices, and assume, moreover, that it is only needed to support
such queries as long as $G$ contains $\Omega(\Delta)$ short edge-disjoint
$s$-$t$ paths. It was observed in [CK24] that, in such a case, the running
time of the algorithm of [BGWN20] improves to roughly
$\tilde{O}(n^{2}+\Gamma\cdot n/\Delta)$. This observation was one of the key
insights that allowed them to obtain a faster running time for the special
case of the $s$-$t$-SP problem, and for Maximum Bipartite Matching.

We now provide additional relevant details of the algorithm of [CK24]. Like in
[BGS20], the $\mathsf{MaintainCluster}$ problem is exploited in order to
maintain an $\mathcal{ATO}$ of the input graph $H$. Initially, the clustering
${\mathcal{X}}$ contains three clusters: $S=\left\\{s\right\\}$,
$T=\left\\{t\right\\}$, and $U=V(H)\setminus\left\\{s,t\right\\}$. The
algorithm for the $\mathsf{MaintainCluster}$ problem is then initialized on
graph $H[U]$, with an appropriately chosen distance parameter $d_{U}$. In
general, whenever a new cluster $X$ joins ${\mathcal{X}}$, the algorithm for
the $\mathsf{MaintainCluster}$ problem is initialized on $H[X]$. Whenever that
algorithm produces a sparse cut $(A,B)$ in $X$, we select a subset
$Z\in\left\\{A,B\right\\}$ of vertices to be deleted from $X$, update $X$ by
deleting these vertices, and add $Z$ as a new cluster to ${\mathcal{X}}$,
after which the algorithm for the $\mathsf{MaintainCluster}$ problem is
initialized on $H[Z]$. The key idea is that, since the cuts produced by the
algorithm for the $\mathsf{MaintainCluster}$ problem are sparse, we can ensure
that the total span of all right-to-left edges is sufficiently small. If we
then consider the contracted graph $\hat{H}$, this, in turn, ensures that the
total width of all right-to-left edges in $\hat{H}$ is low. We can now apply
the algorithm of [BGWN20] for decremental SSSP on almost-DAG’s to support
approximate shortest $s$-$t$ path queries in $\hat{H}$, while exploiting the
fact that such queries only need to be supported as long as $\hat{H}$ contains
a large number of short edge-disjoint $s$-$t$ paths, in order to speed it up.
For every cluster $X\in{\mathcal{X}}$, we can then use the algorithm for the
$\mathsf{MaintainCluster}$ problem on $H[X]$, in order to respond to
approximate shortest-path queries between pairs of vertices in $X$. Combining
these data structures together, we can support approximate shortest $s$-$t$
path queries in the original graph $H$, as long as $H$ contains many short
edge-disjoint $s$-$t$ paths. This high-level approach allows one to obtain
algorithms for decremental $s$-$t$-SP, and for the $\mathsf{RouteAndCut}$
problem, from algorithms for the $\mathsf{MaintainCluster}$ problem, that we
now discuss in more detail.

##### The $\mathsf{MaintainCluster}$ problem.

To recap, in the $\mathsf{MaintainCluster}$ problem, the input is a graph $G$
that undergoes an online sequence of edge deletions, and a distance parameter
$d$. The goal is to efficiently support short-path queries: given a pair $x,y$
of vertices of $G$, return a path of length at most $d$ connecting them in
$G$. The algorithm may, however, at any time, produce a cut $(A,B)$ in $G$ of
sparsity at most $O\left(\frac{\operatorname{poly}\log n}{d}\right)$,
following which, the vertices of one side of the cut are deleted from $G$. The
algorithm is used in order to maintain individual clusters of the
$\mathcal{ATO}$. A similar problem was considered by [BGS20], who provide an
algorithm with total update time $\widehat{O}(|E(G)|\cdot d^{2})$ for it,
where the time to respond to each query is roughly proportional to the number
of edges on the path that the algorithm returns. In [CK24] this problem was
considered in a more relaxed setting, where the number of queries that the
algorithm must support is bounded by a given parameter $\Delta$, and the goal
is to minimize the total running time of the algorithm, that is, the sum of
the total update time, and the time required to respond to all queries. The
algorithm of [CK24] for this setting has running time
$\widetilde{O}(|E(G)|\cdot d+|V(G)|^{2})\cdot\max\left\\{1,\frac{\Delta\cdot
d^{2}}{|V(G)|}\right\\}$, which, for the specific parameters that they employ,
becomes $\widetilde{O}(|E(G)|\cdot d+|V(G)|^{2})$. In order to obtain our
improved algorithm for Maximum Bipartite Matching, we need to generalize this
result so that it works for a wider range of parameters, achieving running
time $|V(G)|^{2+o(1)}$.

The algorithm of [CK24] follows a rather standard approach. First, they use
the Cut-Matching game in order to compute a large expander graph $\hat{G}$,
and to embed it into $G$ via short paths that cause low congestion. The
algorithm for the Cut Player is implemented in a rather straightforward
manner, since they can afford a running time that is as high as
$\Theta(|V(\hat{G})|^{2})$. The algorithm for the Matching Player essentially
needs to solve an instance of the $\mathsf{RouteAndCut}$ problem. Using the
MWU approach as before, it can be reduced to solving an instance of directed
decremental SSSP. The algorithm of [CK24] then uses the standard Even-Shiloach
tree data structure in order to solve the latter problem. In addition to the
expander $\hat{G}$ and its embedding into $G$, the algorithm of [CK24]
maintains two additional Even-Shilach trees in $G$. Both trees are rooted in
the vertices of $\hat{G}$, and have depth roughly $d$. One of the trees has
all its edges directed away from the root, and the other has all of its edges
directed towards the root. In order to respond to a query between a pair $x,y$
of vertices of $G$, the two Even-Shiloach trees are used to compute a short
path connecting $x$ to some vertex $x^{\prime}\in V(\hat{G})$, and a short
path connecting some vertex $y^{\prime}\in V(\hat{G})$ to $y$. A simple BFS
search in the expander $\hat{G}$ then yields a short path connecting
$x^{\prime}$ to $y^{\prime}$, which can be turned into an
$x^{\prime}$-$y^{\prime}$ path in $G$ by exploiting the embedding of $\hat{G}$
into $G$.

We now describe several sources of inefficiency of the algorithm of [CK24],
and then describe our approach to overcoming them. First, both the algorithms
of [CK24] and [BGS20] for the $\mathsf{MaintainCluster}$ problem are only
designed for graphs with unit edge-length. However, both of these works solve
(a variant of) the SSSP problem in graphs with arbitrary edge lengths. To
overcome this difficulty, [CK24] use the same approach as [BGS20]: namely,
they choose a threshold $\tau$, and initially delete all edges whose length is
greater than $\tau$ (called _long edges_) from the input graph $H$. The
lengths of the remaining edges (called _short edges_) are set to $1$ for the
sake of maintaining the $\mathcal{ATO}$ and solving the
$\mathsf{MaintainCluster}$ problem on the resulting instances. The long edges
however are reinserted into the contracted graph $\hat{H}$, and the actual
lengths of the short edges are used in it as well. This approach unfortunately
results in a rather large number of right-to-left edges with a large width in
$\hat{H}$, as it may potentially include all long edges. In order to overcome
this difficulty, we design an algorithm for the $\mathsf{MaintainCluster}$
problem that can handle arbitrary edge lengths, which adds an additional
dimension of technical challenges.

The second main source of inefficiency in the algorithm of [CK24] is their use
of Even-Shiloach trees in their algorithm for $\mathsf{MaintainCluster}$, both
in implementing the Matching Player in the Cut-Matching game, and in order to
maintain short paths connecting all vertices of $G$ to the vertices of the
expander $\hat{G}$. It is immediate to see that the problem that the Matching
Player needs to solve is essentially an instance of the $\mathsf{RouteAndCut}$
problem. We also observe that an algorithm for a variant of the
$\mathsf{RouteAndCut}$ problem can be exploited in order to maintain the paths
connecting all vertices of $G$ to the vertices of $V(\hat{G})$. We abstract
this as a new problem, that we call $\mathsf{ConnectToCenters}$, and discuss
it below. We believe that this problem and our algorithm for solving it are of
independent interest. We remark that this reduction from the
$\mathsf{ConnectToCenters}$ problem to the $\mathsf{RouteAndCut}$ problem
requires that the algorithm for the $\mathsf{RouteAndCut}$ problem works for
arbitrary congestion parameter $\eta\leq\Delta$, and this is the reason for
our more general definition of the $\mathsf{RouteAndCut}$ problem.

To summarize, as already shown in previous work, in order to obtain an
efficient algorithm for the $\mathsf{RouteAndCut}$ problem, it is enough to
obtain an efficient algorithm for the $\mathsf{MaintainCluster}$ problem, and
we observe that the opposite is also true: an efficient algorithm for the
$\mathsf{RouteAndCut}$ problem implies an efficient algorithm for the
$\mathsf{MaintainCluster}$ problem. This, however, creates a chicken-and-egg
issue, where in order to solve one of the two problems efficiently, we need to
design an efficient algorithm for the other. We overcome this barrier by using
a recursive approach, that we describe next.

##### A recursive approach.

We parameterize both the $\mathsf{RouteAndCut}$ and the
$\mathsf{MaintainCluster}$ problem using a parameter $r>0$. We say that an
instance of the $\mathsf{MaintainCluster}$ problem on an $n$-vertex graph $G$
with a distance parameter $d$ is $r$-restricted, if $d\leq 2^{r\cdot\sqrt{\log
n}}$. Consider now an instance of the $\mathsf{RouteAndCut}$ problem on an
$n$-vertex graph $H$, with two subsets $A,B$ of its vertices, and parameters
$\Delta$ and $\eta$. It is not hard to see that, if ${\mathcal{P}}$ is any
collection of $\Omega(\Delta/\operatorname{poly}\log n)$ paths connecting
vertices of $A$ to vertices of $B$, that cause vertex-congestion at most
$\eta$, then a large fraction of the paths in ${\mathcal{P}}$ have length
$\tilde{O}(n\eta/\Delta)$. We say that an instance of the
$\mathsf{RouteAndCut}$ problem is $r$-restricted if $\frac{n\eta}{\Delta}\leq
2^{r\cdot\sqrt{\log n}}$. We show a straightforward algorithm for the
$1$-restricted $\mathsf{RouteAndCut}$ problem. Then for all $r\geq 1$, we show
that an efficient algorithm for the $r$-restricted $\mathsf{RouteAndCut}$
problem implies an efficient algorithm for the $r$-restricted
$\mathsf{MaintainCluster}$ problem. We also show that an efficient algorithm
for the $r$-restricted $\mathsf{MaintainCluster}$ problem implies an efficient
algorithm for the $(r+1)$-restricted $\mathsf{RouteAndCut}$ problem. Using
induction on $r$, we then simultaneously obtain efficient algorithms for the
$\mathsf{RouteAndCut}$ and the $\mathsf{MaintainCluster}$ problems for the
entire range of values for the parameter $r$.

#####  $\mathsf{ConnectToCenters}$ Problem.

The $\mathsf{ConnectToCenters}$ problem is employed as a subroutine in the
algorithm for the $\mathsf{MaintainCluster}$ problem, but we feel that it is
interesting in its own right, as it seems to arise in many different settings.
Suppose we are given a dynamic $n$-vertex graph $G$; for now we will assume
that $G$ undergoes an online sequence of edge deletions, but in fact our
algorithm considers other updates, as described later. In addition to graph
$G$, assume that we are given a parameter $d$, and a subset $T\subseteq V(G)$
of vertices that we call _centers_. The goal is to maintain, for every vertex
$v\in V(G)$, a path $P(v)$ of length at most $d$, connecting $v$ to some
vertex of $T$. As the time progresses, some vertices may be deleted from $T$,
but we are guaranteed that $T$ always contains a large enough fraction of the
vertices of $G$, e.g. $|T|\geq\Omega(|V(G)|/(d\operatorname{poly}\log n)$. In
order to ensure that the deletion of edges from $G$ does not impact too many
paths in ${\mathcal{P}}^{*}=\left\\{P(v)\mid v\in V(G)\right\\}$, it is
desirable that the paths cause a small edge-congestion (say at most
$\tilde{O}(d)$), and for similar reasons it is desirable that every vertex
$x\in T$ serves as an endpoint of relatively few such paths (say at most
$\tilde{O}(d)$). At any time, the algorithm may compute a cut $(A,B)$ of
sparsity at most $O\left(\frac{\operatorname{poly}\log n}{d}\right)$, with
$|A\cap T|\ll|A|$, after which the vertices of $A$ are deleted from $G$ and
the algorithm continues. We note that whenever the by now standard paradigm of
embedding an expander into the input graph $G$ and then maintaining short
paths connecting all vertices of $G$ to the vertices of the expander is used,
one essentially needs to solve a variant of the $\mathsf{ConnectToCenters}$
problem. So far this was typically done by employing Even-Shiloach trees, but
this data structure becomes inefficient once the depth parameter $d$ is
sufficiently large. It is for this reason that we believe that our algorithm
for the $\mathsf{ConnectToCenters}$ problem is of independent interest.

It is immediate to see that the initial collection
${\mathcal{P}}^{*}=\left\\{P(v)\mid v\in V(G)\right\\}$ of paths of length
$O(d)$ each, connecting every vertex of $G$ to some vertex of $T$, that cause
edge-congestion $\tilde{O}(d)$, can be computed by employing an algorithm for
the $\mathsf{RouteAndCut}$ problem. As edges are deleted from $G$, and
vertices are deleted from $T$, some of the paths in ${\mathcal{P}}^{*}$ may be
destroyed. Whenever a path $P(v)\in{\mathcal{P}}^{*}$ is destroyed (whether
because its last endpoint is deleted from $T$, or because one of its edges is
deleted from $G$), we say that vertex $v$ becomes _disconnected_. We then need
to _reconnect_ all disconnected vertices to $T$. This, again, can be done by
employing an algorithm for the $\mathsf{RouteAndCut}$ problem, but doing so
directly may be very inefficient. Assume, for example, that we are given an
algorithm ${\mathcal{A}}$ for the $\mathsf{RouteAndCut}$ problem, that, on an
$n$-vertex graph $G$, has running time $O(n^{2+o(1)})$. Every time a subset of
vertices of $G$ becomes disconnected, we would need to employ this algorithm
in order to reconnect them to $T$. However, it is possible that only a small
number of vertices become disconnected at a time, and spending
$\Theta(n^{2+o(1)})$ time to reconnect them each time is prohibitively
expensive. A better approach seems to be to consider the set $U$ of vertices
that are currently connected, and the set $U^{\prime}$ of vertices that are
currently disconnected. We could then attempt to route the vertices of
$U^{\prime}$ to the vertices of $U$ by constructing a new collection
${\mathcal{Q}}=\left\\{Q(u)\mid u\in U^{\prime}\right\\}$ of paths, where each
path $Q(u)$ connects $u$ to some vertex of $U$; and then exploit the existing
paths in $\left\\{P(v)\mid v\in U\right\\}$ in order to compute paths
connecting every vertex of $U^{\prime}$ to the vertices of $T$. However, we
cannot afford to spend $\Theta(n^{2})$ time in order to compute the set
${\mathcal{Q}}$ of paths. On the other hand, intuitively, if $|U^{\prime}|\ll
U$, then we may not need to explore the entire graph $G$ in order to compute
the set ${\mathcal{Q}}$ of paths. In order to overcome this difficulty, we
require that the algorithm for the $\mathsf{RouteAndCut}$ problem has running
time roughly $n^{1+o(1)}\cdot(n-|B|)$, instead of $n^{2+o(1)}$. In particular,
if the graph $G$ is sufficiently dense and $|B|$ is sufficiently large, then
this running time may be much smaller than $|E(G)|$. Our reduction from the
$(r+1)$-restricted $\mathsf{RouteAndCut}$ problem to the $r$-restricted
$\mathsf{MaintainCluster}$ problem follows the high-level approach of [BGS20]
and [CK24]. However, this additional strict requirement on the efficiency of
the algorithm for the $\mathsf{RouteAndCut}$ problem, in addition to the
requirement that the algorithm should work for arbitrary values of the
congestion parameter $\eta$, make the reduction more challenging and
technical.

Assume now that we are given an algorithm ${\mathcal{A}}$ for the
$\mathsf{RouteAndCut}$ problem, that, on an instance $(G,A,B,\Delta,\eta)$ has
running time $n^{1+o(1)}\cdot(n-|B|)$, where $n=|V(G)|$. As described above,
in order to implement our algorithm for the $\mathsf{ConnectToCenters}$
problem, whenever we are given a collection $U^{\prime}$ of vertices that are
currently disconnected from $T$, we can now employ Algorithm ${\mathcal{A}}$
to construct a collection ${\mathcal{Q}}$ of paths connecting them to the
vertices of $U$ (the set of currently connected vertices), and then compose
${\mathcal{Q}}$ with the collection $\left\\{P(v)\mid v\in U\right\\}$ of
paths to obtain the desired collection $\left\\{P(v)\mid v\in
U^{\prime}\right\\}$ of paths that reconnects the vertices of $U^{\prime}$ to
$T$. Unfortunately, if we follow this approach, and keep appending paths to
each other iteration after iteration, we may obtain paths whose lengths are
prohibitively large. Instead, we follow a _layered_ approach. For a parameter
$\lambda=O(\log n)$, we maintain at all times a partition
$(U_{0},\ldots,U_{\lambda})$ of the vertices of $G$ into _layers_ , where
$U_{0}=T$, and $U_{\lambda}$ contains all vertices that are currently
disconnected. For all $1\leq i<\lambda$, we also maintain a collection
${\mathcal{Q}}_{i}=\left\\{K(v)\mid v\in U_{i}\right\\}$ of paths, where each
path $K(v)$ connects a vertex $v\in U_{i}$ to a vertex in
$\bigcup_{i^{\prime}=0}^{i-1}U_{i^{\prime}}$. The paths in each set
${\mathcal{Q}}_{i}$ have length at most $\frac{d}{4\lambda}$, and cause
congestion $\tilde{O}(d)$ in $G$. By composing the paths from different sets
${\mathcal{Q}}_{i}$, we can obtain, for every vertex $v\in V(G)$, a path that
connects it to some vertex of $T$. At a high level, for all $1\leq i<\lambda$,
we reconstruct layer $U_{i}$ and the set ${\mathcal{Q}}_{i}$ of paths from
scratch every time that roughly $2^{\lambda-i}$ new vertices become
disconnected, and we also ensure that $|U_{i}|\leq 2^{\lambda-i}$ holds.
Therefore, when we employ the algorithm for the $\mathsf{RouteAndCut}$ problem
in order to reconnect the vertices of $U_{i}$, in the resulting instance of
$\mathsf{RouteAndCut}$, $n-|B|\leq 2^{\lambda-i}$ holds, and the running time
of the algorithm is roughly $n^{1+o(1)}\cdot 2^{\lambda-i}$. Therefore, as
index $i$ becomes smaller, the running time of the $\mathsf{RouteAndCut}$
algorithm that is used to reconnect the vertices of $U_{i}$ increases.
However, for smaller values of index $i$, we need to reconstruct the set
$U_{i}$ of vertices and the set ${\mathcal{Q}}_{i}$ of paths less often. This
eventually leads to the desired $n^{2+o(1)}$ running time.

##### Edge-deletion versus edge-length-increase updates.

We would like to highlight here what we feel is a somewhat surprising insight
from our work, that may appear minor at first sight, but we believe that it
may be useful in other problems. Consider the following two settings for
dynamic graphs: the first one is the standard decremental setting, where edges
are deleted from the input graph $G$ as the time progresses. The second
setting is a somewhat more unusual one, where the only updates that are
allowed in the input graph $G$ is the doubling of the lengths of its edges; we
refer to this type of updates as edge-length-increases. Generally, it is not
hard to see that both models are roughly equivalent. Indeed, in order to
simulate edge-length-increases in the standard decremental setting, we can
simply create a large number of copies of each edge $e$ of various lengths,
and then, as the length of $e$ increases, some of these copies are deleted.
The reduction in the other direction is also immediate: we can simulate the
deletion of an edge $e$ from $G$ by repeatedly doubling its length, until it
becomes very high.

The dynamic graphs that arise from using the MWU framework typically only
undergo edge-length-increase updates, which are then typically implemented as
edge-deletions, in order to reduce the problem to the more standard
decremental SSSP, as described above. However, the edge-length-increases that
the input graph $G$ undergoes under this implementation of the MWU method are
rather well-behaved: specifically, the lengths of the edges are only increased
moderately, and all length increases occur on the edges that participate in
the paths that the algorithm returns in response to queries. We observe that
the resulting SSSP problem appears to be easier if we work with edge-length-
increase updates directly, instead of the more traditional approach of
transforming them into edge-deletion updates.

In order to illustrate this, consider the following simple scenario: we are
given a graph $G$, and initially the length of every edge in $G$ is $1$.
Assume also that we have computed another graph $X$ (it may be convenient to
think of $X$ as an expander), and embedded $X$ into $G$ via paths of length at
most $d$, that cause edge-congestion at most $\eta$. If some edge $e$ is
deleted from $G$, then every edge $\hat{e}\in E(X)$, whose embedding path
$Q(\hat{e})$ uses $e$, must be deleted from $X$ as well. Therefore, the
deletion of a single edge from $G$ may lead to the deletion of $\eta$ edges
from $X$. Assume now that, instead, the edges of $G$ only undergo increases in
their lengths, where the length of each edge may be iteratively doubled, but
the total increase in the lengths of all edges is moderate. If the length of
an edge $e\in E(G)$ is doubled, then for every edge $\hat{e}\in E(X)$ whose
embedding path $Q(\hat{e})$ uses $e$, the length of $Q(\hat{e})$ increases
only slightly, and so there is no need to delete $\hat{e}$ from $E(X)$. We can
usually wait until the length of the path $Q(\hat{e})$ increases significantly
before edge $\hat{e}$ needs to be deleted from $X$. As mentioned already, in
instances arising from the MWU framework, the total increase in the lengths of
all edges in $G$ over the course of the entire algorithm is usually not very
large, and in particular most edges whose lengths are doubled are short. This
allows us to maintain the expander $X$ and its embedding into $G$ over the
course of a much longer sequence of updates to $G$. This is one of the
insights that allowed us to obtain a more efficient algorithm for the
$\mathsf{MaintainCluster}$ problem.

To summarize, our algorithm departs from the algorithm of [CK24] in the
following key aspects. First, we use the MWU method to reduce the
$\mathsf{RouteAndCut}$ problem to $s$-$t$-SP in dynamic graphs that undergo
edge-length-increases instead of edge-deletion updates. Second, our algorithm
for the $\mathsf{RouteAndCut}$ problem has running time that significantly
decreases when the set $B$ of vertices contains almost all vertices of $G$; in
some cases the running time may even be lower than $|E(G)|$. We extend the
$\mathsf{MaintainCluster}$ problem to handle arbitrary edge lengths, but
unlike [CK24] we only allow edge-length-increases, instead of edge-deletion
updates. We design an algorithm for the $\mathsf{ConnectToCenters}$ problem,
that we believe is of independent interest, and that can be viewed as reducing
the $\mathsf{MaintainCluster}$ problem to $\mathsf{RouteAndCut}$. Lastly, we
use a recursive approach, in which algorithms for $\mathsf{RouteAndCut}$ rely
on algorithms for $\mathsf{MaintainCluster}$ and vice versa, by parametrizing
both problems with an auxiliary parameter $r$, and then inductively develop
algorithms for both problems for the entire range of $r$.

###  1.2 Organization

We start with preliminaries in Section 2. We then provide a high-level
overview of our algorithm in Section 3, where we also define the
$\mathsf{RouteAndCut}$ and the $s$-$t$-SP problems, state our main results for
them, and describe the modification of the MWU method that we use. In Section
4 we define the $\mathsf{MaintainCluster}$ problem and state our main result
for it. We also describe our recursive approach, state the theorems describing
the reductions between the $\mathsf{MaintainCluster}$ and the
$\mathsf{RouteAndCut}$ problems, and complete the algorithm for the Maximum
Bipartite Matching problem using them. Then in Section 5 we describe our
reduction from the $(r+1)$-restricted $\mathsf{RouteAndCut}$ problem to the
$r$-restricted $\mathsf{MaintainCluster}$ problem. In Section 6 we describe
our algorithm for the $\mathsf{ConnectToCenters}$ problem, and in Section 7 we
complete our reduction from the $r$-restricted $\mathsf{MaintainCluster}$
problem to the $r$-restricted $\mathsf{RouteAndCut}$ problem.

##  2 Preliminaries

In this paper we work with both directed and undirected graphs. By default
graphs are not allowed to contain parallel edges or self-loops. Graphs with
parallel edges are explicitly referred to as _multigraphs_.

##### Congestion of Paths and Flows.

Let $G$ be a graph with capacities $c(e)\geq 0$ on edges $e\in E(G)$, and let
${\mathcal{P}}$ be a collection of simple paths in $G$. We say that the paths
in ${\mathcal{P}}$ cause _edge-congestion_ $\eta$ if every edge $e\in E(G)$
participates in at most $\eta\cdot c(e)$ paths in ${\mathcal{P}}$. When edge
capacities are not explicitly given, we assume that they are unit. If every
edge of $G$ belongs to at most one path in ${\mathcal{P}}$, then we say that
the paths in ${\mathcal{P}}$ are _edge-disjoint_.

Similarly, if we are given a flow value $f(e)\geq 0$ for every edge $e\in
E(G)$, we say that flow $f$ causes edge-congestion $\eta$ if, for every edge
$e\in E(G)$, $f(e)\leq\eta\cdot c(e)$ holds. If $f(e)\leq c(e)$ holds for
every edge $e\in E(G)$, we may say that $f$ causes _no edge-congestion_.

Assume now that we are given a graph $G$, a pair $s,t$ of its vertices, and a
collection ${\mathcal{P}}$ of simple paths connecting $s$ to $t$. We say that
the paths in ${\mathcal{P}}$ cause _vertex-congestion_ $\eta$ if every vertex
$v\in V(G)\setminus\left\\{s,t\right\\}$ participates in at most $\eta$ paths.
If the paths in ${\mathcal{P}}$ cause vertex-congestion $1$, then we say that
they are _internally vertex-disjoint_.

Throughout the paper, by default, when we talk about congestion caused by a
set of paths or by a flow, we mean edge-congestion.

##### Embeddings of Graphs.

Let $H,G$ be two graphs with $V(H)\subseteq V(G)$. An _embedding_ of $H$ into
$G$ is a collection ${\mathcal{P}}=\left\\{P(e)\mid e\in E(H)\right\\}$ of
simple paths in $G$, where for every edge $e=(u,v)\in E(H)$, path $P(e)$
connects $u$ to $v$ in $G$. The _congestion_ of the embedding is the maximum,
over all edges $e^{\prime}\in E(G)$, of the number of paths in ${\mathcal{P}}$
containing $e^{\prime}$; equivalently, it is the edge-congestion that the set
${\mathcal{P}}$ of paths causes in $G$.

##### Cuts, Sparsity and Expanders for Directed Graphs.

Let $G$ be a directed graph. A _cut_ in $G$ is a an ordered pair $(A,B)$ of
subsets of vertices of $G$, such that $A\cap B=\emptyset$, $A\cup B=V(G)$, and
$A,B\neq\emptyset$. Note that we do not require that $|A|\leq|B|$ in this
definition. The _sparsity_ of the cut is:

$\Phi(A,B)=\frac{|E(A,B)|}{\min{\left\\{|A|,|B|\right\\}}}.$

We say that a directed graph $G$ is a $\varphi$-expander, for a given value
$0<\varphi<1$, if the sparsity of every cut in $G$ is at least $\varphi$.
Notice that, if $G$ is a $\varphi$-expander, then for every partition $(A,B)$
of its vertices, both $|E(A,B)|\geq\varphi\cdot\min\left\\{|A|,|B|\right\\}$
and $|E(B,A)|\geq\varphi\cdot\min{\left\\{|A|,|B|\right\\}}$ hold.

We also use the following theorem that provides a fast algorithm for an
explicit construction of an expander, that is based on the results of Margulis
[Mar73] and Gabber and Galil [GG81]. The proof for undirected graphs was shown
in [CGL+20].

######  Theorem 2.1 (Theorem 2.4 in [CGL+20]).

There is a constant $\alpha_{0}>0$ and a deterministic algorithm, that we call
$\mathsf{ConstructExpander}$, that, given an integer $n>1$, constructs a
directed graph $H_{n}$ with $|V(H_{n})|=n$, such that $H_{n}$ is an
$\alpha_{0}$-expander, and every vertex in $H_{n}$ has at most $9$ incoming
and at most $9$ outgoing edges. The running time of the algorithm is $O(n)$.

The above theorem was proved in [CGL+20] for undirected expanders, with
maximum vertex degree in the resulting expander bounded by $9$. It is easy to
adapt this result to directed expanders: if a graph $G$ is an undirected
$\varphi$-expander, and a directed graph $G^{\prime}$ is obtained from $G$ by
replacing every edge with a pair of bi-directed edges, then it is easy to
verify that $G^{\prime}$ is a directed $\varphi$-expander.

We will also use the following simple observation, that shows that a slight
modification of an expander graph still results in a (somewhat weaker)
expander. Similar observations were shown in previous work for undirected
graphs (see e.g. Observation 2.3 in [CGL+20]).

######  Observation 2.2.

Let $H$ be a directed $n$-vertex graph, that is a $\varphi$-expander, for some
parameter $0<\varphi<1$. Let $H^{\prime}$ be a graph that is obtained from $H$
as follows. We select an arbitrary set $X$ of $n^{\prime}\leq n$ vertices of
$H$, add a set $Y$ of $n^{\prime}$ new vertices to $H$, and add two matchings
of cardinality $n^{\prime}$ to $H$: a matching $M^{\prime}\subseteq X\times Y$
and a matching $M^{\prime\prime}\subseteq Y\times X$. Then the resulting graph
$H^{\prime}$, defined over $(n+n^{\prime})$ vertices, is a
$\varphi/3$-expander.

###### Proof.

Consider any cut $(A,B)$ in $H^{\prime}$. Assume first that $|A\cap
Y|\geq\frac{2|A|}{3}$. Recall that every vertex $y\in Y$ has one edge
$e_{y}=(y,y^{\prime})\in M^{\prime\prime}$ with $y^{\prime}\in X$. Let
$Y_{1}\subseteq A\cap Y$ denote the set of all vertices $y\in A\cap Y$ whose
corresponding vertex $y^{\prime}$ lies in $A$, and let $Y_{2}$ denote the set
of all remaining vertices of $A\cap Y$. Since $|A\setminus Y|\leq\frac{|A\cap
Y|}{2}$, it must be the case that $|Y_{2}|\geq|Y_{1}|\geq\frac{|A|}{3}$. But
then the edges of $M^{\prime\prime}$ that are incident to the vertices of
$Y_{2}$ belong to $E_{H^{\prime}}(A,B)$, and so
$|E_{H^{\prime}}(A,B)|\geq|Y_{2}|\geq\frac{|A|}{3}$.

Similarly, if $|B\cap Y|\geq\frac{2|B|}{3}$, then, by using a similar argument
with the edges of the matching $M^{\prime}$ instead of $M^{\prime\prime}$, we
get that $|E_{H^{\prime}}(A,B)|\geq\frac{|B|}{3}$. Therefore, if either
$|A\cap Y|\geq\frac{2|A|}{3}$, or $|B\cap Y|\geq\frac{2|B|}{3}$ hold, then the
sparsity of the cut $(A,B)$ is at least $\frac{1}{3}$.

It now remains to consider the case where both $|A\cap Y|<\frac{2|A|}{3}$ and
$|B\cap Y|<\frac{2|B|}{3}$ hold. Let $A^{\prime}=A\setminus Y$ and
$B^{\prime}=B\setminus Y$. Notice that $|A^{\prime}|\geq|A|/3$ and
$|B^{\prime}|\geq|B|/3$ must hold. Then $(A^{\prime},B^{\prime})$ is a cut in
graph $H$, and, since $H$ is a $\varphi$-expander,
$|E_{H}(A^{\prime},B^{\prime})|\geq\varphi\cdot\min\left\\{|A^{\prime}|,|B^{\prime}|\right\\}\geq\frac{\varphi}{3}\cdot\min\left\\{|A|,|B|\right\\}$.
Since $E_{H}(A^{\prime},B^{\prime})\subseteq E_{H^{\prime}}(A,B)$, we get that
the sparsity of the cut $(A,B)$ in $H^{\prime}$ is at least
$\frac{\varphi}{3}$.

The following simple observation follows from the standard ball-growing
technique, and similar observations were used in many previous works,
including in [CK24], where a proof is provided for completeness.

######  Observation 2.3 (Observation 2.2 in full version of [CK24]).

There is a deterministic algorithm, that, given a directed $n$-vertex graph
$G=(V,E)$ with unit edge lengths and maximum vertex degree at most
$\delta_{\mbox{{\footnotesize{max}}}}$, together with two vertices $x,y\in V$
with $\mbox{\sf dist}_{G}(x,y)\geq d$ for some parameter $d\geq
64\delta_{\mbox{{\footnotesize{max}}}}\log n$, computes a cut $(A,B)$ of
sparsity at most $\varphi=\frac{32\delta_{\mbox{{\footnotesize{max}}}}\log
n}{d}$ in $G$. The running time of the algorithm is
$O(\delta_{\mbox{{\footnotesize{max}}}}\cdot\min\left\\{|A|,|B|\right\\})$.

We will also use the following simple observation a number of times.
Intuitively, the observation allows us to convert a sequence of small sparse
cuts into a single balanced sparse cut; a proof of this observation appears in
[CK24].

######  Observation 2.4 (Observation 2.3 in full version of [CK24]).

There is a deterministic algorithm, whose input consists of a directed
$n$-vertex graph $G$, parameters $0<\alpha<1$ and $0\leq\varphi\leq 1$, and a
sequence ${\mathcal{X}}=(X_{1},X_{2},\ldots,X_{k})$ of subsets of vertices of
$G$, such that the following hold:

  * •

Every vertex of $V(G)$ lies in exactly one set in
$\left\\{X_{1},\ldots,X_{k}\right\\}$;

  * •

$\max_{i}\left\\{|X_{i}|\right\\}=\alpha n$; and

  * •

for all $1\leq i<k$, if we denote by
$X^{\prime}_{i}=\bigcup_{j=i+1}^{k}X_{j}$, then either
$|E(X_{i},X^{\prime}_{i})|\leq\varphi\cdot|X_{i}|$, or
$|E(X^{\prime}_{i},X_{i})|\leq\varphi\cdot|X_{i}|$.

The algorithm computes a cut $(A,B)$ in $G$ with
$|A|,|B|\geq\min\left\\{\frac{1-\alpha}{2}\cdot n,\frac{n}{4}\right\\}$, and
$|E_{G}(A,B)|\leq\varphi\cdot\sum_{i=1}^{k-1}|X_{i}|$. The running time of the
algorithm is $O(|E(G)|)$.

##### Chernoff Bound.

We use the following standard version of Chernoff Bound (see. e.g., [DP09]).

######  Lemma 2.5 (Chernoff Bound).

Let $X_{1},\ldots,X_{n}$ be independent randon variables taking values in
$\left\\{0,1\right\\}$. Let $X=\sum_{1\leq i\leq n}X_{i}$, and let
$\mu=\text{\bf E}\left[X\right]$. Then for any $t>2e\mu$,

$\Pr\Big{[}X>t\Big{]}\leq 2^{-t}.$

Additionally, for any $0\leq\delta\leq 1$,

$\Pr\Big{[}X<(1-\delta)\cdot\mu\Big{]}\leq e^{-\frac{\delta^{2}\cdot\mu}{2}}.$

###  2.1 Even-Shiloach Tree for Weighted Directed Graphs

We use the generalization of the Even-Shiloach data structure of [ES81, Din06]
to weighted directed graphs, due to [Kin99], who extended similar results of
[HK95] for unweighted directed graphs.

######  Theorem 2.6 ([Kin99], see Section 2.1).

There is a deterministic algorithm, whose input consists of a directed graph
$H$ with integral edge lengths, a source vertex $s\in V(H)$, and a distance
parameter $d\geq 1$. The algorithm maintains a shortest-path tree
$\tau\subseteq H$ rooted in $s$, up to depth $d$. In other words, for every
vertex $v\in V(H)$ with $\mbox{\sf dist}_{H}(s,v)\leq d$, vertex $v$ lies in
the tree $\tau$, and the length of the shortest $s$-$v$ path in $\tau$ is
equal to that in $H$. The data structure also maintains, for all $v\in
V(\tau)$, the current value $\mbox{\sf dist}_{H}(s,v)$. The total update time
of the algorithm is $O(|E(H)|\cdot d)$.

We will sometimes refer to the data structure from Theorem 2.6 as
$\mbox{\sf{ES-Tree}}(H,s,d)$.

###  2.2 The Adjacency-List Representation of Graphs

In some of the problems that we consider, the algorithm may not need to
explore the entire input graph $G$, and in some cases, it is important that
the running time of the algorithm is strictly smaller than $|E(G)|$. As an
example, consider the following routing problem: we are given as input a
directed graph $G$, and two disjoint sets $A$,$B$ of its vertices. The goal is
to compute a largest-cardinality collection ${\mathcal{P}}$ of paths, where
each path $P\in{\mathcal{P}}$ connects a vertex of $A$ to a vertex of $B$, the
paths in ${\mathcal{P}}$ cause low edge-congestion, and every vertex of $A\cup
B$ serves as an endpoint of at most one path in ${\mathcal{P}}$. We emphasize
that vertices of $A\cup B$ may serve as inner vertices on paths in
${\mathcal{P}}$, and it is possible that some vertex $v\in A\cup B$ serves
both as an endpoint of some path in ${\mathcal{P}}$, and as an inner vertex on
several other paths. Consider now a scenario where almost all vertices of $G$
lie in $B$. In such a case, one can show that there is an optimal solution
${\mathcal{P}}$ to the problem, such that only a small number of vertices of
$B$ participate in the paths in ${\mathcal{P}}$. In other words, in order to
compute such a collection of paths, it is not necessary to explore the entire
graph $G$. In such cases, we will often be ineterested in algorithms with
running time roughly $O(n^{1+o(1)}\cdot(n-|B|))$, that may be significantly
smaller than $|E(G)|$, if graph $G$ is sufficiently dense. Therefore, we will
need to provide the input graph $G$ to the algorithm in a way that allows it
to achieve this low running time, and does not require spending
$\Omega(|E(G)|)$ time in order to read the entire input.

In such cases, we will often require that the (directed) input graph $G$ is
provided to the algorithm in the adjacency-list model: we are given two arrays
$\operatorname{OUT}$ and $\operatorname{IN}$ of length $n$ each. For all
$1\leq i\leq n$, entry $\operatorname{OUT}[i]$ contains a pointer to a linked-
list, that contains all edges in set $\delta^{+}(v_{i})$, that is, all edges
that leave the $i$th vertex of $G$. Similarly, $\operatorname{IN}[i]$ contains
a pointer to a linked-list of all edges in $\delta^{-}(v_{i})$ – all edges
that enter the $i$th vertex of $G$. If the edges of $G$ have lengths or
weights, then these lengths or weights also appear in the corresponding lists
$\delta^{-}(v_{i})$ and $\delta^{+}(v_{i})$, where these edges are listed.

Typically, if $\mathsf{Alg}$ is an algorithm for the routing problem mentioned
above, then it will only access the entries
$\operatorname{OUT}[i],\operatorname{IN}[i]$ of a small subset of the vertices
$v_{i}\in V(G)$, allowing us to achieve a running time that is significantly
lower than $\Theta(|E(G)|)$. Specifically, it is sufficient that the algorithm
reads the entries corresponding to the vertices in $V(G)\setminus B$, and of a
small subset of vertices in $B$. This will allow us to obtain running times
for such routing problems roughly of the form
$O(|V(G)|^{1+o(1)}\cdot(|V(G)|-|B|))$, which may be significantly lower than
$\Theta(|E(G)|)$ if set $B$ contains almost all vertices of $G$, and $G$ is
sufficiently dense.

We note that providing the graph $G$ as input to such an algorithm
$\mathsf{Alg}$ may require time $O(|E(G)|+|V(G)|)$, in order to construct the
adjacency-list representation of the input graph $G$. However, in a typical
application, we will construct the adjacency-list representation of the input
graph $G$ once, and then apply Algorithm $\mathsf{Alg}$ for solving the
routing problem on $G$ multiple times, with different vertex sets $A$ and $B$,
possibly with small alterations to the graph $G$ between such executions of
$\mathsf{Alg}$. Therefore, we will not need to construct the adjacency-list
representation of the input graph $G$ from scratch every time Algorithm
$\mathsf{Alg}$ is called.

In some cases, given as input a directed graph $G$ in the adjacency-list
representation, our routing algorithm will need to work with the graph
$\overleftarrow{G}$, which is obtained from $G$ by reversing the directions of
all its edges. In such cases, we can modify the adjacency-list representation
of $G$ to obtain an adjacency-list representation of $\overleftarrow{G}$, by
simply switching the arrays $\operatorname{OUT}$ and $\operatorname{IN}$.

Finally, given a directed graph $G$ and a vertex $v$ in $G$, we will denote by
$\delta^{+}_{G}(v)$, the set of edges leaving $v$, and by $\delta^{-}_{G}(v)$,
the set of edges entering $v$.

###  2.3 Overview of the $\mathcal{ATO}$ framework

We now provide an overview of the Approximate Topological Order
($\mathcal{ATO}$) framework that was developed in [BGWN20] and later used in
[BGS20]. A very slight modification of this framework was also used in [CK24].
We follow here the presentation of [CK24], though we further adapt it to allow
for presence of a special cluster, that contains most of the vertices of the
underlying graph.

Let $G=(V,E)$ be a directed $n$-vertex graph with two special vertices $s$ and
$t$ and non-negative lengths $\ell(e)$ on edges $e\in E$, that undergoes edge-
length-increase updates during a time interval ${\mathcal{T}}$, that we refer
to as the _time horizon_. Throughout, we refer to a collection
$I\subseteq\left\\{1,\ldots,n\right\\}$ of consecutive integers as an
_interval_. The _size_ of the interval $I$, denoted by $|I|$, is the number of
distinct integers in it. An $\mathcal{ATO}$ consists of the following
components:

  * •

a partition ${\mathcal{X}}$ of the set $V$ of vertices of $G$ into non-empty
subsets, such that there is a set $S=\left\\{s\right\\}$ and
$T=\left\\{t\right\\}$ in ${\mathcal{X}}$;

  * •

(optional) a single set $U\in{\mathcal{X}}$ that we refer to as a _special
cluster_ , together with an integer $1\leq\gamma\leq|U|$;

If special cluster $U$ is defined, then all other sets of ${\mathcal{X}}$ are
called _regular clusters_. If the special cluster is undefined, then all sets
of ${\mathcal{X}}$ are called regular clusters, and we set $\gamma=1$; and

  * •

a map $\rho$, that maps every set $X\in{\mathcal{X}}$ to an interval
$I_{X}\subseteq\left\\{1,\ldots,n-\gamma+1\right\\}$. The size of the interval
$I_{X}$ must be $|X|$ if $X$ is a regular cluster, and $|X|-\gamma+1$, if it
is a special cluster. We require that all intervals in $\left\\{I_{X}\mid
X\in{\mathcal{X}}\right\\}$ are mutually disjoint.

For convenience, we will denote an $\mathcal{ATO}$ by
$({\mathcal{X}},\rho,U,\gamma)$, where the special cluster $U$ may be
undefined. Both the partition ${\mathcal{X}}$ and the map $\rho$ evolve over
time. We denote by ${\mathcal{X}}^{(\tau)}$ the partition ${\mathcal{X}}$ at
time $\tau$, and by $\rho^{(\tau)}$ the map $\rho$ at time $\tau$. For every
set $X\in{\mathcal{X}}^{(\tau)}$, we denote by $I^{{}^{(\tau)}}_{X}$ the
interval $I_{X}$ associated with $X$ at time $\tau$. If the special cluster
$U$ is defined in the initial $\mathcal{ATO}$, then we require that
$U\in{\mathcal{X}}$ holds at all times, though some vertices may be deleted
from $U$ as the time progresses, and, additionally, $|U|\geq\gamma$ must hold
at all times.

The only type of changes that are allowed to the $\mathcal{ATO}$ over time is
the splitting of the clusters $X\in{\mathcal{X}}$. In order to split a set
$X\in{\mathcal{X}}$, we select a subset $Y\subseteq X$ of vertices (if $X$ is
a special cluster, then $|X\setminus Y|\geq\gamma$ must hold, while otherwise
we require that $X\setminus Y\neq\emptyset$). We add $Y$ to ${\mathcal{X}}$ as
a new cluster, and we delete the vertices of $Y$ from $X$. We also partition
interval $I_{X}$ into two disjoint subintervals: one of these subintervals, of
length $|Y|$, becomes the interval $I_{Y}$ that is associated with the new
cluster $Y$. The other subinterval, whose length is $|X|$ if $X$ is a regular
cluster, and $|X|-\gamma+1$ if it is a special cluster, becomes the new
interval $I_{X}$ associated with the cluster $X$. Note that the total length
of the two new intervals is equal to the length of the original interval
$I_{X}$.

Notice that an $\mathcal{ATO}$ $({\mathcal{X}},\rho,U,\gamma)$ naturally
defines a left-to-right ordering of the intervals in $\left\\{I_{X}\mid
X\in{\mathcal{X}}\right\\}$: we will say that interval $I_{X}$ lies to the
left of interval $I_{X^{\prime}}$, and denote $I_{X}\prec I_{X^{\prime}}$ iff
every integer in interval $I_{X}$ is smaller than every integer in
$I_{X^{\prime}}$. We will also sometimes denote $X\prec X^{\prime}$ in such a
case. Notice also that, if we are given an ordering
$\sigma=(X_{1},X_{2},\ldots,X_{k})$ of the sets in ${\mathcal{X}}$, then this
ordering naturally defines the map $\rho$, where for all $1\leq i\leq k$, the
first integer in $I_{X_{i}}$ is $\sum_{j=1}^{i-1}|X_{j}|+1$ if none of the
clusters in $\left\\{X_{1},\ldots,X_{i-1}\right\\}$ is special, and it is
$\sum_{j=1}^{i-1}|X_{j}|-\gamma+2$ otherwise. For convenience, we will denote
the map $\rho$ associated with the ordering $\sigma$ by $\rho(\sigma)$.

Given a vertex $v\in V$, we will sometimes denote by $X^{v}$ the set of
${\mathcal{X}}$ that contains $v$. Consider now some edge $e=(u,v)$ in graph
$G$, and assume that $X^{u}\neq X^{v}$. We say that $e$ is a _left-to-right_
edge if $X^{u}\prec X^{v}$, and we say that it is a _right-to-left_ edge
otherwise.

Lastly, we denote by $H=G_{|{\mathcal{X}}}$ the _contracted graph_ associated
with $G$ and ${\mathcal{X}}$ – the graph that is obtained from $G$ by
contracting every set $X\in{\mathcal{X}}$ into a vertex $v_{X}$, that we may
call a _supernode_ , to distinguish it from other vertices of $G$. We keep
parallel edges but discard any self-loops.

##### Intuition.

For intuition, we could let ${\mathcal{X}}$ be the set of all strongly
connected components of the graph $G$. The corresponding contracted graph
$H=G_{|{\mathcal{X}}}$ is then a DAG, so we can define a topological order of
its vertices. This order, in turn, defines an ordering $\sigma$ of the sets in
${\mathcal{X}}$, and we can then let the corresponding $\mathcal{ATO}$ be
$({\mathcal{X}},\rho(\sigma),U,\gamma)$, where $U$ is undefined and
$\gamma=1$. Notice that in this setting, all edges of $G$ that connect
different sets in ${\mathcal{X}}$ are left-to-right edges. However, we will
not follow this scheme. Instead, we will ensure that every set
$X\in{\mathcal{X}}$ corresponds to some expander-like graph, and we will allow
both left-to-right and right-to-left edges with respect to the
$\mathcal{ATO}$. It would still be useful to ensure that the corresponding
contracted graph $H$ is close to being a DAG, since there are good algorithms
for SSSP on DAG’s and DAG-like graphs. Therefore, we will try to limit both
the number of right-to-left edges, and their “span”, that we define below.

##### Skip and Span of Edges.

For every edge $e=(u,v)\in E(G)$ we define two values: the _skip_ of edge $e$,
denoted by $\operatorname{skip}(e)$, and the _span_ of $e$, denoted by
$\operatorname{span}(e)$. Intuitively, the skip value of an edge $(u,v)$ will
represent the “distance” between the intervals $I_{X^{u}}$ and $I_{X^{v}}$.
Non-zero span values are only assigned to right-to-left edges. The span value
also represents the distance between the corresponding intervals, but this
distance is defined differently. We now formally define the span and skip
values for each edge, and provide an intuition for them below.

Consider some edge $e=(x,y)\in E(G)$. Let $X,Y\in{\mathcal{X}}$ be the sets
containing $x$ and $y$, respectively. If $X=Y$, then
$\operatorname{skip}(e)=\operatorname{span}(e)=0$.

Assume now that $X\prec Y$, that is, $e$ is a left-to-right edge. In this
case, we set $\operatorname{span}(e)=0$, and we let $\operatorname{skip}(e)$
be the distance between the last endpoint of $I_{X}$ and the first endpoint of
$Y$. In other words, if the largest integer in $I_{X}$ is $Z_{X}$, and the
smallest integer in $Y$ is $A_{Y}$, then $\operatorname{skip}(e)=A_{Y}-Z_{X}$.
Note that, as the algorithm progresses, sets $X$ and $Y$ may be partitioned
into smaller subsets. It is then possible that $\operatorname{skip}(e)$ may
grow over time, but it may never decrease.

Lastly, assume that $Y\prec X$, so $e$ is a right-to-left edge. In this case,
we set $\operatorname{skip}(e)$ to be the distance between the right endpoint
of $I_{Y}$ and the left endpoint of $I_{X}$, and we let
$\operatorname{span}(e)$ be the distance between the left endpoint of $I_{Y}$
and the right endpoint of $I_{X}$. In other words, if $A_{X}$ and $Z_{X}$ are
the smallest and the largest integers in $X$ respectively, and similarly
$A_{Y}$ and $Z_{Y}$ are the smallest and the largest integers in $Y$
respectively, then $\operatorname{skip}(e)=A_{X}-Z_{Y}$ and
$\operatorname{span}(e)=Z_{X}-A_{Y}$ (see Figure 1). Notice that, as the
algorithm progresses, and sets $X$ and $Y$ are partitioned into smaller
subsets, the value $\operatorname{span}(e)$ may only decrease, while the value
$\operatorname{skip}(e)$ may only grow. Moreover,
$\operatorname{skip}(e)\leq\operatorname{span}(e)$ always holds.

Figure 1: Skip and span values of a right-to-left edge.

For intuition, consider again the setting where ${\mathcal{X}}$ represents the
strongly connected components of $G$, and $\rho=\rho(\sigma)$, where $\sigma$
is an ordering of the sets in ${\mathcal{X}}$ corresponding to a topological
ordering of the vertices of $H=G_{|{\mathcal{X}}}$. Then for any path $P$ in
$G$, $\sum_{e\in E(P)}\operatorname{skip}(e)\leq n$ must hold. This is because
the path must traverse the sets of ${\mathcal{X}}$ in their left-to-right
order. Consider now inserting a single right-to-left edge $e=(x,y)$ into $G$,
so $x\in X$, $y\in Y$, and $Y\prec X$. In this case, path $P$ will generally
traverse the sets in ${\mathcal{X}}$ from left to right, but it may use the
edge $e$ in order to “skip” back. It is not hard to see that
$\sum_{e^{\prime}\in E(P)}\operatorname{skip}(e^{\prime})\leq
n+\operatorname{skip}(e)+\operatorname{span}(e)$ now holds, since, by
traversing the edge $e$, path $P$ is ‘set back’ by at most
$\operatorname{span}(e)$ units. In other words, path $P$ traverses the sets in
${\mathcal{X}}$ in their left-to-right order, except when it uses the edge $e$
to “skip” to the left. The length of the interval it “skips” over is bounded
by $\operatorname{span}(e)$, so this skip adds at most
$\operatorname{skip}(e)+\operatorname{span}(e)\leq 2\operatorname{span}(e)$ to
$\sum_{e^{\prime}\in E(P)}\operatorname{skip}(e^{\prime})$.

Using the same intuitive reasoning, if we allow graph $G$ to contain an
arbitrary number of right-to-left edges, then for any simple path $P$,
$\sum_{e\in E(P)}\operatorname{skip}(e)\leq n+\sum_{e\in
E(G)}2\operatorname{span}(e)$ holds. However, if we are given any collection
${\mathcal{P}}$ of edge-disjoint paths in $G$, then there must be some path
$P\in{\mathcal{P}}$ with $\sum_{e\in E(P)}\operatorname{skip}(e)\leq
n+\frac{\sum_{e\in E(G)}2\operatorname{span}(e)}{|{\mathcal{P}}|}$, since
every edge $e\in E(G)$ may contribute the value $2\operatorname{span}(e)$ to
at most one path in ${\mathcal{P}}$. We will use this fact extensively.

##### From $\mathcal{ATO}$ to SSSP in DAG-like Graphs.

Like the algorithm of [BGS20] for decremental SSSP, our algorithm relies on
two main technical tools. The first tool allows us to maintain the partition
${\mathcal{X}}$ of $V(G)$ over time. Intuitively, we will ensure that, for
every set $X\in{\mathcal{X}}$, the corresponding induced subgraph $G[X]$ of
$G$ is in some sense expander-like. In particular, we will be able to support
short-path queries between vertices of $X$ efficiently. When $G[X]$ is no
longer an expander-like graph, we will compute a sparse cut $(A,B)$ in this
graph, and we will replace $X$ with $A$ and $B$ in ${\mathcal{X}}$ (though
formally we will think about this process as splitting the cluster $X$: we add
a new cluster, $A$ or $B$, to ${\mathcal{X}}$, and then delete the vertices of
this new cluster from $X$). Some of the edges connecting the sets $A$ and $B$
may become right-to-left edges with respect to the current $\mathcal{ATO}$
$({\mathcal{X}},\rho)$ that we maintain. We will control the number of such
edges and their $\operatorname{span}$ values by ensuring that the cut is
$\varphi$-sparse, for an appropriately chosen parameter $\varphi$.

Given a dynamically evolving $\mathcal{ATO}$ $({\mathcal{X}},\rho,U,\gamma)$
for graph $G$, we can now construct the corresponding contracted graph
$H=G_{|{\mathcal{X}}}$. For convenience, the supernodes of $H$ representing
the sets $S=\left\\{s\right\\}$ and $T=\left\\{t\right\\}$ of ${\mathcal{X}}$
are denoted by $s$ and $t$, respectively. Notice that, as the time progresses,
graph $H$ undergoes, in addition to edge-length-increase updates (that we will
implement as edge-deletions using standard methods) another type of updates,
that we call _vertex-splitting_ : whenever some set $X\in{\mathcal{X}}$
undergoes a splitting, and a new cluster $Y\subseteq X$ is inserted into
${\mathcal{X}}$, we need to insert a supernode corresponding to $Y$ into $H$,
and then possibly delete some edges that are incident to $v_{X}$ from $H$. We
will say that the new supernode $v_{Y}$ was _split off_ from the supernode
$v_{X}$. Consider now any edge $e=(x,y)\in E(G)$, and assume that $x\in Z$ and
$y\in Z^{\prime}$ for some $Z,Z^{\prime}\in{\mathcal{X}}$ with $Z\neq
Z^{\prime}$. The length of the edge $e$ in graph $H$ remains the same:
$\ell(e)$. We will also associate, with every edge $e\in E(H)$, a _weight_
$w(e)$, that is set to be the smallest integral power of $2$ that is at least
$\operatorname{skip}(e)$. As observed already, as the algorithm progresses,
the value $\operatorname{skip}(e)$ may grow. In order to avoid inserting edges
into $H$ overtime, we will create a number of parallel edges with different
$w(e)$ values corresponding to every edge of $G$ whose endpoints lie in
different clusters of ${\mathcal{X}}$. Specifically, let $e=(x,y)$ be any
edge, with $x\in X$, $y\in Y$, and $X\neq Y$. For every integer $0\leq
i\leq\left\lceil\log n\right\rceil$, such that
$2^{i}\geq\operatorname{skip}(e)$, we add an edge $e_{i}=(v_{X},v_{Y})$ to
$H$, with length $\ell(e)$ and $w(e_{i})=2^{i}$. It is easy to verify that
this construction ensures that, for every vertex $v\in
V(H)\setminus\left\\{t\right\\}$ and integer $0\leq i\leq\left\lceil\log
n\right\rceil$, the number of vertices in the set $\left\\{u\in
V(H)\mid\exists e=(v,u)\in E(H)\mbox{ and }w(e)=2^{i}\right\\}$ is bounded by
$2^{i+2}$. Additionally, by carefully controlling the total span of all right-
to-left edges in graph $G$, we will ensure that there is always a short
$s$-$t$ path $P$ in $H$, such that $\sum_{e\in E(P)}w(e)$ is relatively small.
These two properties are crucial in obtaining a fast algorithm for computing
short $s$-$t$ paths in $H$, as it undergoes edge-deletion and supernode-
splitting updates.

The $\mathcal{ATO}$ framework, combined with an algorithm for maintaining
expander-like graphs, gives rise to the problem of repeately computing short
$s$-$t$ paths in the contracted graph $H$, as it undergoes the updates that we
have outlined above. In [CK24] a problem call DAG-like SSSP was defined, that
abstracts the above problem. They also provided an algorithm for it, which is
essentially identical to the algorithm of [BGWN20]; a similar algorithm was
used in [BGS20]. We now provide the definition of the DAG-like SSSP problem
from [CK24], and summarize their algorithm for it.

###  2.4 SSSP in DAG-like Graphs

The presentation in this section is almost identical to the definition of the
DAG-like SSSP problem from [CK24]. The input to the DAG-like SSSP problem is a
directed multigraph $G=(V,E)$, with two designated vertices $s$ and $t$, a
distance parameter $d>0$, a precision parameter $0<\epsilon\leq 1/8$, such
that $1/\epsilon$ is an integer, and another parameter $\Gamma>0$. Graph $G$
may have parallel edges, but no self-loops. Every edge $e\in E$ of $G$ is
associated with an integral _length_ $\ell(e)>0$, and an additional _weight_
$w(e)$, that must be an integral power of $2$ between $1$ and
$2^{\left\lceil\log n\right\rceil}$. The graph undergoes the following two
types of updates:

  * •

Edge deletion: given an edge $e\in E$, delete $e$ from $G$; and

  * •

Vertex splitting: in this operation, we are given as input a vertex
$v\not\in\left\\{s,t\right\\}$ in the current graph, and new vertices
$u_{1},\ldots,u_{k}$ that need to be inserted into $G$; we may sometimes say
that vertices $u_{1},\ldots,u_{k}$ are _split-off from $v$_. In addition to
vertex $v$ and vertices $u_{1},\ldots,u_{k}$, we are given a new collection
$E^{\prime}$ of edges that must be inserted into $G$, and for every edge $e\in
E^{\prime}$, we are given an integral length $\ell(e)>0$ and a weight $w(e)$
that must be an integral power of $2$ between $1$ and $2^{\left\lceil\log
n\right\rceil}$. For each such edge $e\in E^{\prime}$, either both endpoints
of $e$ lie in $\left\\{u_{1},\ldots,u_{k},v\right\\}$; or one endpoint lies in
$\left\\{u_{1},\ldots,u_{k}\right\\}$, and the other in
$V(G)\setminus\left\\{v,u_{1},\ldots,u_{k}\right\\}$. In the latter case, if
$e=(u_{i},x)$, then edge $e^{\prime}=(v,x)$ must currently lie in $G$, and
both $w(e^{\prime})=w(e)$ and $\ell(e^{\prime})=\ell(e)$ must hold. Similarly,
if $e=(x,u_{i})$, then edge $e^{\prime}=(x,v)$ must currently lie in $G$, and
both $w(e^{\prime})=w(e)$ and $\ell(e^{\prime})=\ell(e)$ must hold.

We let ${\mathcal{T}}$ be the _time horizon_ of the algorithm – that is, the
time interval during which the graph $G$ undergoes all updates. We denote by
$n$ and by $m$ the total number of vertices and edges, respectively, that were
ever present in $G$ during ${\mathcal{T}}$. We assume w.l.o.g. that for every
vertex $v$ that was ever present in $G$, some edge was incident to $v$ at some
time during the update sequence, so $n\leq O(m)$.

For every vertex $v\in V(G)\setminus\left\\{t\right\\}$ and integer $0\leq
i\leq\left\lceil\log n\right\rceil$, we define a set:

$U_{i}(v)=\left\\{u\in V(G)\mid\exists e=(v,u)\in E(G)\mbox{ with
}w(e)=2^{i}\right\\}.$

Note that as the algorithm progresses, each such set $U_{i}(v)$ may change,
with vertices both leaving and joining the set. We require that the following
property must hold at all times $\tau\in{\mathcal{T}}$:

  1. S1.

For every vertex $v\in V(G)\setminus\left\\{t\right\\}$, for every integer
$0\leq i\leq\left\lceil\log n\right\rceil$, $|U_{i}(v)|\leq 2^{i+2}$.

As graph $G$ undergoes edge-deletion and vertex-splitting updates, at any time
the algorithm may be asked a query path-query. It is then required to return a
simple path $P$ connecting $s$ to $t$, whose length $\sum_{e\in E(P)}\ell(e)$
is bounded by $(1+10\epsilon)d$, in time $O(|E(P)|)$.

Lastly, the algorithm may return FAIL at any time and halt. It may only do so
if the current graph $G$ does not contain any $s$-$t$ path $P$ with
$\sum_{e\in E(P)}\ell(e)\leq d$, and $\sum_{e\in E(P)}w(e)\leq\Gamma$.

The following theorem provides an algorithm for the DAG-like SSSP problem. Its
formal proof, presented in [CK24], follows almost immediately from the results
of [BGWN20]. Specifically, Theorem 5.1 of [BGWN20] provides a similar result
with a slightly different setting of parameters, but their arguments can be
easily extended to prove the theorem below, as was shown in [CK24].

######  Theorem 2.7 (Theorem 5.1 in the full version of [CK24]).

There is a deterministic algorithm for the DAG-like SSSP problem with total
update time $\tilde{O}\left(\frac{n^{2}+m+\Gamma\cdot
n}{\epsilon^{2}}\right)$; here, $m$ and $n$ are the total number of edges and
vertices, respectively, that were ever present in $G$.

##  3 High-Level Overview of the Algorithm

In this section we provide the definitions of well-structured graphs and well-
structured cuts, that are used throughout the paper. We also define a new
problem, called $\mathsf{RouteAndCut}$, which is one of the main building
blocks of our algorithm. We then state the main theorem for this section, that
provides an efficient algorithm for the $\mathsf{RouteAndCut}$ problem, and we
show that our main result – the proof of Theorem 1.1 follows from it. The
proof of the theorem that provides an algorithm for the $\mathsf{RouteAndCut}$
problem is by induction, and is provided in the remainder of this paper. In
this section we also provide a simple and somewhat inefficient algorithm for
the $\mathsf{RouteAndCut}$ problem, that will be used as the induction base.
We also define an intermediate problem, called $r$-Restricted $s$-$t$-SP
problem, and show that an algorithm for this problem implies an algorithm for
the $\mathsf{RouteAndCut}$ problem. We start by defining well-structured
graphs and well-structured cuts.

###  3.1 Well-Structured Graphs and Well-Structured Cuts

Throughout the paper we will work with special kinds of directed graphs, that
for convenience we call _well-structured graphs_ , and define below.

######  Definition 3.1 (Well-Structured Graphs).

Let $G=(L,R,E)$ be a bipartite directed graph. We call the edges of
$E_{G}(L,R)$ _regular_ and the edges of $E_{G}(R,L)$ _special_. We say that
$G$ is a _well-structured graph_ , if every vertex of $G$ is incident to at
most one special edge. If every vertex of $G$ is incident to exactly one
special edge, then we say that $G$ is a _perfect well-structured graph_.

If $G$ is a well-structured graph, then we assume that the partition $(L,R)$
of its vertices is given as part of the description of $G$. We will sometimes
consider well-structured graphs with lengths on their edges, and we will
sometimes restrict our attention to assignments of lengths to edges that have
special properties, that we define below. We call such assignments of lengths
to edges _proper_.

######  Definition 3.2 (Proper Assignment of Edge Lengths).

Let $G=(L,R,E)$ be a well-structured directed graph, and let $\ell(e)\geq 0$
be an assignment of lengths to the edges $e\in E$. We say that
$\left\\{\ell(e)\right\\}_{e\in E}$ is a _proper_ assignment of edge lengths,
if, for every regular edge $e\in E$, $\ell(e)=0$, and for every special edge
$e\in E$, $\ell(e)$ is an integral power of $2$ with $\ell(e)\geq 1$. If, for
every special edge $e\in E$, $\ell(e)=1$ holds, then we say that
$\left\\{\ell(e)\right\\}_{e\in E}$ is a _proper uniform assignment of edge
lengths_.

Recall that a _cut_ in a graph $G$ is an ordered pair $(A,B)$ of non-empty
subsets of $V(G)$ with $A\cap B=\emptyset$ and $A\cup B=V$. We will often use
the notion of a well-structured cut, that is defined next.

######  Definition 3.3 (Well-Structured Cut).

Let $G=(L,R,E)$ be a well-structured graph, and let $(A,B)$ be a cut in $G$.
We say that $(A,B)$ is a _weakly well-structured cut_ , or just a _well-
structured cut_ , if all edges of $E_{G}(A,B)$ are special edges. If,
additionally, all edges in $E_{G}(B,A)$ are regular edges, then we say that
$(A,B)$ is a _strongly_ well-structured cut.

###  3.2 The RouteAndCut problem

In this subsection we define the $\mathsf{RouteAndCut}$ problem, which is one
of the main building blocks of our algorithm. Before we do so, we need to
define the notion of _routing_.

######  Definition 3.4 (Routing).

Let $G=(V,E)$ be a directed graph, and let $A,B$ be two disjoint subsets of
its vertices. A _partial routing_ , or just a _routing_ , from $A$ to $B$ is a
collection ${\mathcal{Q}}$ of paths in $G$, such that every path in
${\mathcal{Q}}$ connects a vertex of $A$ to a vertex of $B$, and the endpoints
of the paths in ${\mathcal{Q}}$ are all disjoint. The _congestion_ of the
routing is the edge-congestion that the set ${\mathcal{Q}}$ of paths causes in
graph $G$. Vertices of $A\cup B$ may serve both as endpoints and as inner
vertices of the paths in ${\mathcal{Q}}$ simultaneously. A partial routing of
cardinality $|A|$ is called a _complete_ routing.

We are now ready to define the $\mathsf{RouteAndCut}$ problem, and its special
case, called $r$-restricted $\mathsf{RouteAndCut}$. Intuitively, we use the
notion of the $r$-restricted $\mathsf{RouteAndCut}$ problem in order to
discretize the problem instances: our algorithm for $\mathsf{RouteAndCut}$
will consider, by induction, $r$-restricted instances of the problem, from
smaller to larger values of $r$.

######  Definition 3.5 ($\mathsf{RouteAndCut}$ problem).

The input to the $\mathsf{RouteAndCut}$ problem is a well-structured
$n$-vertex graph $G=(L,R,E)$, that is given in the adjacency-list
representation, parameters $N\geq n$, $\Delta\geq 1$, and
$1\leq\eta\leq\Delta$, and two disjoint subsets $A,B$ of vertices of $G$, with
$|A|,|B|\geq\Delta$.

The output of the problem is a (possibly partial) routing ${\mathcal{Q}}$ from
$A$ to $B$, whose congestion is bounded by $4\eta\log N$. Additionally, if
$|{\mathcal{Q}}|<\Delta$, the output must contain 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, if $A^{\prime}\subseteq A,B^{\prime}\subseteq B$ denote the subsets
of vertices that do not serve as endpoints of the paths in ${\mathcal{Q}}$,
then $A^{\prime}\subseteq X$ and $B^{\prime}\subseteq Y$ hold. The algorithm
for the $\mathsf{RouteAndCut}$ problem is also allowed to return “FAIL”
without producing any output, but the probability of the algorithm doing so
must be bounded by $1/2$.

We say that an instance $(G,A,B,\Delta,\eta,N)$ of the $\mathsf{RouteAndCut}$
problem is _$r$ -restricted_, for an integer $1\leq r\leq\left\lceil\sqrt{\log
N}\right\rceil$, iff $\frac{(n-|B|)\cdot\eta}{\Delta}\leq 2^{r\cdot\sqrt{\log
N}}$ holds.

We provide a brief intuition for the parameters $\Delta$ and $N$ in the
definition of the $\mathsf{RouteAndCut}$ problem, and for the definition of
$r$-restricted instances. Consider an arbitrary well-structured $n$-vertex
graph $G$, two disjoint sets $A,B$ of its vertices and a parameter $\eta$, and
assume that we need to compute a large routing from $A$ to $B$ in $G$, with
congestion at most $\eta$. Typically, we will set $\Delta$ to be the
cardinality of the desired routing (and if it is not known, we can set
$\Delta=\min\left\\{|A|,|B|\right\\}$). Initially, we will also set $N=n$, and
consider the resulting instance $(G,A,B,\Delta,\eta,N)$ of the
$\mathsf{RouteAndCut}$ problem. Now suppose we compute a routing from $A$ to
$B$ in graph $G$ of cardinality $\Delta$ that causes edge-congestion at most
$\eta$. Assume w.l.o.g. that, if $b\in B$ is an inner vertex on some path of
the routing, then it serves as an endpoint of some other path of the routing.
Then it is not hard to show that most of the paths in the routing must have
length at most $d=O\left(\frac{(n-|B|)\cdot\eta}{\Delta}\right)$. The
definition or $r$-restricted instances requires that this parameter $d$ is
roughly bounded by $2^{r\sqrt{\log N}}$. It is easy to see that our starting
instance is $r^{*}$-restricted, for $r^{*}=\left\lceil\sqrt{\log
N}\right\rceil$. In order to solve this problem instance, we will need to
solve the problem recursively on smaller subgraphs $G^{\prime}$ of $G$, but it
is important for us to ensure that the resulting instances are
$r^{\prime}$-restricted, for $r^{\prime}<r^{*}$. In order to do so, we will
let the parameter $N$ in the resulting subinstances correspond to the number
of vertices in the original graph $G$ (we may need to slightly adjust it for
technical reasons but the adjustments are minor). By appropriately setting the
parameters $\Delta$ and $\eta$ for the resulting subinstances, we can then
ensure that they are indeed $r^{\prime}$-restricted, for some
$r^{\prime}<r^{*}$. Overall, the parameter $N$ can be thought of as roughly
the number of vertices in the original instance of the $\mathsf{RouteAndCut}$
problem that we try to solve, and it is used mostly to define the notion of
$r$-restricted instances. The notion of $r$-restricted instances allows us to
construct algorithms for the $\mathsf{RouteAndCut}$ problem inductively, by
going from smaller to larger values of $r$.

The following theorem provides one of our main technical results, namely an
efficient algorithm for the $\mathsf{RouteAndCut}$ problem.

######  Theorem 3.6.

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

The remainder of this paper is largely dedicated to the proof of Theorem 3.6,
but first we show that the proof of Theorem 1.1 follows from it.

###  3.3 Completing the Proof of Theorem 1.1

Recall that in the Maximum Bipartite Matching problem, the input is a simple
undirected $n$-vertex bipartite graph $G=(L,R,E)$, and the goal is to compute
a matching of maximum cardinality in $G$.

We can assume w.l.o.g. that we are given a target integral value $C^{*}>0$. If
$C^{*}\leq\mathsf{OPT}$, then our algorithm must either produce a matching of
cardinality $C^{*}$, or terminate with a “FAIL”, but we require that the
algorithm terminates with a “FAIL” with probability at most
$1/\operatorname{poly}(n)$ in this case. If $C^{*}>\mathsf{OPT}$, then our
algorithm may return an arbitrary matching, or terminate with a “FAIL”.

We can make this assumption w.l.o.g. since we can use a standard technique of
performing a binary search over the value $\mathsf{OPT}$ of the optimal
solution. We use bounds $W<W^{\prime}$ on the value of the optimal solution,
initializing $W=1$ and $W^{\prime}=n$, and we start with $C^{*}=\left\lfloor
n/2\right\rfloor$. Given the current guess $C^{*}$ on $\mathsf{OPT}$, we run
the algorithm with this target value $C^{*}$. If the algorithm successfully
computes a matching of cardinality at least $C^{*}$, then we set $W=C^{*}$,
and otherwise, we set $W^{\prime}=C^{*}$. In either case, we select the next
value $C^{*}=\left\lfloor\frac{W^{\prime}-W}{2}\right\rfloor$ and continue.
Once $W^{\prime}-W\leq 1$ holds, we run the algorithm once with
$C^{*}=W^{\prime}$ and once with $C^{*}=W$, and then output the better of the
two solutions. We say that an algorithm _errs_ in an iteration, if it returns
“FAIL”, but $C^{*}\leq\mathsf{OPT}$ holds in that iterations. Notice that, if
the algorithm never errs, then after $O(\log n)$ iterations it is guaranteed
to terminate with an optimal matching. Since the probability that the
algorithm errs in a single iteration is bounded by $1/\operatorname{poly}(n)$,
and the number of iterations is bounded by $O(\log n)$, the algorithm is
guaranteed to return an optimal matching with probability at least
$1-1/\operatorname{poly}(n)$.

From now on, we assume that we are given a target value $C^{*}$, and that $G$
contains a matching of cardinality $C^{*}$. Our algorithm must either compute
a matching of cardinality $C^{*}$, or to return “FAIL”, but the probability
for returning “FAIL” must be bounded by $1/\operatorname{poly}(n)$. For
convenience, we denote $C^{*}$ by $\mathsf{OPT}$. We can assume that $n$ is
greater than a large enough constant, since otherwise the problem can be
solved in $O(1)$ time.

It is well known that the Maximum Bipartite Matching problem can be reduced to
computing maximum $s$-$t$ flow in a directed flow network with unit edge
capacities. In order to do so, we start with the graph $G$, and direct all its
edges from the vertices of $L$ towards the vertices of $R$. We then add a
source vertex $s$, that connects with an edge to every vertex of $L$, and a
destination vertex $t$, to which every vertex of $R$ is connected. All edge
capacities are set to $1$. Let $G^{\prime}$ denote the resulting directed flow
network. It is easy to verify that the value of the maximum $s$-$t$ flow in
$G^{\prime}$ is equal to the cardinality of maximum matching in $G$. Moreover,
given an integral flow $f$ in $G^{\prime}$, we can compute a matching $M$ of
cardinality $\operatorname{val}(f)$ in $G$, in time $O(n)$: we simply include
in $M$ all edges of $G$ that carry $1$ flow unit.

Our algorithm consists of $O(\log^{3}n)$ phases. Throughout the algorithm, we
maintain a matching $M$ in $G$, starting with $M=\emptyset$, and we denote
$\Delta^{*}=\mathsf{OPT}-|M|$. If $M$ is the matching at the beginning of a
phase, and $M^{\prime}$ is the matching obtained at the end of the phase, then
we require that $|M^{\prime}|\geq|M|+\Omega(\Delta^{*}/\log^{2}n)$, where
$\Delta^{*}=\mathsf{OPT}-|M|$. We show a combinatorial algorithm, that, given
an initial matching $M$, either returns “FAIL”, or computes such a matching
$M^{\prime}$, in time $O\left(n^{2}\cdot 2^{O(\sqrt{\log n}\log\log
n)}\right)$, where the probability that the algorithm returns “FAIL” is
bounded by $1/\operatorname{poly}(n)$. This will ensure that the number of the
phases is bounded by $O(\log^{3}n)$, and the total running time of the
algorithm is $O\left(n^{2}\cdot 2^{O(\sqrt{\log n}\log\log n)}\right)$. From
now on we focus on the description of a single phase.

##### Implementation of a Single Phase.

We assume that we are given some matching $M$ in the input graph $G$, and we
denote $\Delta^{*}=\mathsf{OPT}-|M|$. Our goal is to compute a matching
$M^{\prime}$ of cardinality at least $|M|+\Omega(\Delta^{*}/\log^{2}n)$. As
observed already, matching $M$ defines a flow $f$ of value $|M|$ in the
directed flow network $G^{\prime}$ with unit edge capacities. We denote by
$H=G^{\prime}_{f}$ the corresponding residual flow network, and we say that
$H$ is the _residual flow network of $G$ with respect to matching $M$_.
Observe that $H$ is a directed flow network with unit edge capacities, and
that the value of the maximum $s$-$t$ flow in $H$ is at least
$\mathsf{OPT}-|M|=\Delta^{*}$.

Next, we will define an instance of the $\mathsf{RouteAndCut}$ problem.
Consider first the graph $H^{\prime}=H\setminus\left\\{s,t\right\\}$. Notice
that, for every edge $e=(u,v)$ of $G$ with $u\in L$ and $v\in R$, if $e\in M$,
then edge $(v,u)$ is present in $H^{\prime}$, and otherwise edge $(u,v)$ is
present in $H^{\prime}$. Therefore, all edges of $H^{\prime}$ that are
directed from vertices of $R$ to vertices of $L$ correspond to the edges of
the current matching $M$. Clearly, every vertex of $H^{\prime}$ may be
incident to at most one edge of $E_{H^{\prime}}(R,L)$, and so graph
$H^{\prime}$ is a well-structured graph.

We let $A\subseteq L$ be the set of vertices $v$, such that edge $(s,v)$ is
present in graph $H$, and we let $B\subseteq R$ be the set of vertices $u$,
such that edge $(u,t)$ is present in $H$. We also define parameters $\eta=1$,
$N=n$, and $\Delta=\Delta^{*}$. It is easy to verify that
$(H^{\prime},A,B,\Delta,\eta,N)$ is a valid input to the
$\mathsf{RouteAndCut}$ problem, and we can compute an adjacency-list
representation of $H^{\prime}$ in time $O(|E(G)|)$. Recall that there is an
$s$-$t$ flow $f$ of value $\Delta^{*}$ in graph $H$, and, from the integrality
of maximum flow in integer-capacity networks, we can assume that this flow is
integral. This flow naturally defines a routing ${\mathcal{Q}}^{*}$ from $A$
to $B$, that causes congestion $\eta=1$, with
$|{\mathcal{Q}}^{*}|=\Delta^{*}$.

We apply the algorithm from Theorem 3.6 to instance
$(H^{\prime},A,B,\Delta,\eta,N)$ of the $\mathsf{RouteAndCut}$ problem. As
long as the algorithm returns “FAIL”, we keep executing it, for up to
$\left\lceil 100\log n\right\rceil$ iterations. If the algorithm from Theorem
3.6 returned “FAIL” in all $\left\lceil 100\log n\right\rceil$ consecutive
iterations, we terminate our algorithm and return “FAIL”. It is easy to verify
that this may happen with probability at most $1/n^{100}$. Otherwise, the
algorithm from Theorem 3.6 must return a routing ${\mathcal{Q}}$ from $A$ to
$B$ with congestion at most $4\log n$. We show that
$|{\mathcal{Q}}|\geq\frac{\Delta^{*}}{\log n}$ must hold in the next
observation.

######  Observation 3.7.

If ${\mathcal{Q}}$ is the routing returned by the algorithm from Theorem 3.6,
then $|{\mathcal{Q}}|\geq\frac{\Delta^{*}}{\log n}$.

###### Proof.

Let $A^{\prime}\subseteq A,B^{\prime}\subseteq B$ denote the subsets of
vertices that do not serve as endpoints of the paths in ${\mathcal{Q}}$.
Assume for contradiction that $|{\mathcal{Q}}|<\frac{\Delta^{*}}{\log n}$.

Recall that the algorithm from Theorem 3.6 must also return a cut $(X,Y)$ in
$H^{\prime}$ with
$|E_{H^{\prime}}(X,Y)|\leq\frac{64\Delta^{*}}{\log^{4}n}+256|{\mathcal{Q}}|\leq\frac{512\Delta^{*}}{\log
n}$, such that $A^{\prime}\subseteq X$ and $B^{\prime}\subseteq Y$. Also,
recall that we have established that there is a routing ${\mathcal{Q}}^{*}$
from $A$ to $B$ in $H^{\prime}$ of cardinality at least $\Delta^{*}$, that
causes edge-congestion $1$. Since $|{\mathcal{Q}}|<\frac{\Delta^{*}}{\log n}$,
at least $\frac{\Delta^{*}}{2}$ of the paths in ${\mathcal{Q}}^{*}$ must
originate at vertices of $A^{\prime}$ and terminate at vertices of
$B^{\prime}$. Each such path must contain an edge of $E_{H^{\prime}}(X,Y)$, so
$|E_{H^{\prime}}(X,Y)|\geq\frac{\Delta^{*}}{2}$ must hold, a contradiction.

Notice that the paths in ${\mathcal{Q}}$ naturally define a collection
${\mathcal{Q}}^{\prime}$ of at least $\frac{\Delta^{*}}{\log n}$ $s$-$t$ paths
in graph $H$ (the residual flow network with respect to $G$ and the current
matching $M$), and they cause congestion at most $4\log n$ (since the
endpoints of the paths in ${\mathcal{Q}}$ are disjoint). Next, we show an
algorithm that computes a collection ${\mathcal{Q}}^{\prime\prime}$ of
$\Omega\left(\frac{\Delta^{*}}{\log^{2}n}\right)$ edge-disjoint $s$-$t$ paths
in graph $H$. We will then use the paths in ${\mathcal{Q}}^{\prime\prime}$ in
order to augment the current flow $f$ in graph $G^{\prime}$, which, in turn,
will allow us to compute the new augmented matching $M$.

In order to compute the collection ${\mathcal{Q}}^{\prime\prime}$ of paths, we
construct a directed graph $H^{\prime\prime}\subseteq H$, that consists of all
vertices and edges that participate in the paths of ${\mathcal{Q}}^{\prime}$.
The capacity of every edge in $H^{\prime\prime}$ remains unit – the same as
its capacity in $H$. Next, we show that $|E(H^{\prime\prime})|\leq O(n\log
n)$, and that there is an $s$-$t$ flow of value at least
$\frac{\Delta^{*}}{4\log^{2}n}$ in $H^{\prime\prime}$.

######  Observation 3.8.

$|E(H^{\prime\prime})|\leq O(n\log n)$, and there is an $s$-$t$ flow of value
at least $\frac{\Delta^{*}}{4\log^{2}n}$ in $H^{\prime\prime}$.

###### Proof.

We start by showing that every vertex $v\in
V(H^{\prime\prime})\setminus\left\\{s,t\right\\}$ participates in at most
$8\log n$ paths in ${\mathcal{Q}}^{\prime}$. Indeed, consider any vertex $v\in
V(H^{\prime\prime})\setminus\left\\{s,t\right\\}$, and let
$Q\in{\mathcal{Q}}^{\prime}$ be a path in which vertex $v$ participates.
Assume first that $v\in L$. Then either edge $(s,v)$ belongs to $H$ and lies
on path $Q$, or there is a special edge $(u,v)$ incident to $v$ in $H$, that
lies on path $Q$. Since the paths in ${\mathcal{Q}}^{\prime}$ cause congestion
at most $4\log n$ in $H$, there may be at most $8\log n$ paths in
${\mathcal{Q}}^{\prime}$ that contain either of the edges $(s,v)$ or $(u,v)$,
and so $v$ participates in at most $8\log n$ paths in
${\mathcal{Q}}^{\prime}$. Using a similar argument, every vertex $u\in R$
participates in at most $8\log n$ paths in ${\mathcal{Q}}^{\prime}$.
Therefore, $|E(H^{\prime\prime})|\leq O(n\log n)$.

Consider now a flow in $H^{\prime\prime}$, where we send $\frac{1}{4\log n}$
flow units along every path in ${\mathcal{Q}}^{\prime}$. Since the paths in
${\mathcal{Q}}^{\prime}$ cause congestion at most $4\log n$, this is a valid
$s$-$t$ flow in $H^{\prime\prime}$, and the value of this flow is
$\frac{|{\mathcal{Q}}^{\prime}|}{4\log n}\geq\frac{\Delta^{*}}{4\log^{2}n}$.

Next, we compute an integral maximum $s$-$t$ flow in $H^{\prime\prime}$ that
obeys the edge capacities in $H^{\prime\prime}$, using the standard Ford-
Fulkerson algorithm. We start by setting the flow $f^{\prime}(e)$ on every
edge $e\in E(H^{\prime})$ to $0$, and then perform iterations. In every
iteration, we use the current flow $f^{\prime}$ in $H^{\prime\prime}$ in order
to compute a residual flow network $H^{\prime\prime}_{f^{\prime}}$. If there
is no $s$-$t$ path in $H^{\prime\prime}_{f^{\prime}}$, then the algorithm
terminates. We are then guaranteed that the value of the current flow
$f^{\prime}$ is optimal, so
$\operatorname{val}(f^{\prime})\geq\frac{\Delta^{*}}{4\log^{2}n}$. Otherwise,
we compute an arbitrary $s$-$t$ path $P$ in $H^{\prime\prime}_{f^{\prime}}$,
and we augment the flow $f^{\prime}$ along the path $P$. Notice that every
iteration of the algorithm can be implemented in time
$O(|E(H^{\prime\prime}_{f^{\prime}})|)=\widetilde{O}(n)$, and the number of
iterations is bounded by $n$. Therefore, the total running time of the
algorithm that computes the set ${\mathcal{Q}}^{\prime\prime}$ of paths in
$H^{\prime\prime}$ is $\widetilde{O}(n^{2})$. The final integral flow
$f^{\prime}$ can be decomposed, in time
$O(|E(H^{\prime\prime})|)=\widetilde{O}(n)$, into a collection
${\mathcal{Q}}^{\prime\prime}$ of at least
$\Omega\left(\frac{\Delta^{*}}{\log^{2}n}\right)$ edge-disjoint paths
connecting $s$ to $t$ in $H^{\prime\prime}$. Since $H^{\prime\prime}\subseteq
H$, we have now obtained the desired collection ${\mathcal{Q}}^{\prime\prime}$
of at least $\Omega\left(\frac{\Delta^{*}}{\log^{2}n}\right)$ edge-disjoint
$s$-$t$ paths in $H$.

We note that we could also directly round the initial fractional $s$-$t$ flow
in $H^{\prime\prime}$, in expected time
$\widetilde{O}(|E(H^{\prime\prime})|)=\widetilde{O}(n)$, e.g. by using the
algorithm from Theorem 5 in [LRS13], that builds on the results of [GKK10].
But since their running time is only bounded in expectation, and since the
bottlenecks in the running time of our algorithm lie elsewhere, we instead use
the above simple deterministic algorithm.

We can now augment the current flow in $G^{\prime}$ via the collection
${\mathcal{Q}}^{\prime\prime}$ of augmenting paths, obtaining a new integral
flow in graph $G^{\prime}$ of value $|M|+|{\mathcal{Q}}^{\prime\prime}|$,
which, in turn, defines a new matching $M^{\prime}$ with
$|M^{\prime}|\geq|M|+|{\mathcal{Q}}^{\prime\prime}|\geq|M|+\Omega\left(\frac{\Delta^{*}}{\log^{2}n}\right)$.

We now bound the running time of a single phase. Recall that we may execute
the algorithm from Theorem 3.6 at most $O(\log n)$ times per phase. The
running time of a single execution of the algorithm from Theorem 3.6 is
bounded by $O\left(n^{2}\cdot 2^{O(\sqrt{\log N}\cdot\log\log N)}\right)\leq
O\left(n^{2}\cdot 2^{O(\sqrt{\log n}\cdot\log\log n)}\right)$. Additionally,
the time required to compute the graph $H^{\prime\prime}$, and to compute the
maximum flow in it is bounded by $\widetilde{O}(n^{2})$.

Overall, the running time of a single phase is bounded by $O\left(n^{2}\cdot
2^{O(\sqrt{\log n}\cdot\log\log n)}\right)$. Since the number of phases is
bounded by $O(\log^{3}n)$, the total running time of the algorithm is bounded
by $O\left(n^{2}\cdot 2^{O(\sqrt{\log n}\cdot\log\log n)}\right)$, and the
probability that the algorithm ever returns “FAIL” is bounded by
$1/\operatorname{poly}(n)$.

###  3.4 Proof of Theorem 3.6 – High Level Overview

In order to prove Theorem 3.6, we use two large enough constants $c_{1}\gg
c_{2}$, whose values we set later, and we employ the following theorem.

######  Theorem 3.9.

For all $r\geq 1$, there is a randomized algorithm for the $r$-restricted
$\mathsf{RouteAndCut}$ problem, that, on an input $(G,A,B,\Delta,\eta,N)$ 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}}.$

Note that, if $(G,A,B,\Delta,\eta,N)$ is an instance of the
$\mathsf{RouteAndCut}$ problem, and $|V(G)|=n$, then, from the problem
definition, $\eta\leq\Delta$ and $\frac{(n-|B|)\cdot\eta}{\Delta}\leq n$
holds. Therefore, any instance of the problem is also an instance of
$r^{*}$-restricted $\mathsf{RouteAndCut}$ problem, for
$r^{*}=\left\lceil\sqrt{\log n}\right\rceil$. By using Theorem 3.9 with
parameter $r^{*}=\left\lceil\sqrt{\log n}\right\rceil$, we obtain an algorithm
for the general $\mathsf{RouteAndCut}$ problem whose running time is:

$O\left(n\cdot(n-|B|)\cdot 2^{O(\sqrt{\log N}\cdot\log\log N)}\right).$

Therefore, in order to prove Theorem 3.6, it is enough to prove Theorem 3.9.
In the remainder of this paper we focus on the proof of Theorem 3.9. The proof
is by induction on $r$, and it relies on a slight modification of the
Multiplicative Weight Update (MWU) framework of [GK98, Fle00], that
essentially reduces the $r$-restricted $\mathsf{RouteAndCut}$ problem to a
special case of the directed SSSP problem, that we call $r$-Restricted
$s$-$t$-SP. Before we describe this approach, we describe an algorithm that,
given an instance $(G,A,B,\Delta,\eta,N)$ of the $\mathsf{RouteAndCut}$
problem, constructs a subgraph $G^{\prime}\subseteq G$ with
$V(G^{\prime})=V(G)$ and $|E(G^{\prime})|\leq O((n-|B|)\cdot n)$, such that a
solution to the $\mathsf{RouteAndCut}$ problem instance
$(G^{\prime},A,B,\Delta,\eta,N)$ immediately provides a solution to the
$\mathsf{RouteAndCut}$ problem instance $(G,A,B,\Delta,\eta,N)$.

####  3.4.1 An Auxiliary Graph $G^{\prime}$ and its Properties

Consider an instance $(G=(L,R,E),A,B,\Delta,\eta,N)$ of the $r$-restricted
$\mathsf{RouteAndCut}$ problem, for an integer $1\leq
r\leq\left\lceil\sqrt{\log N}\right\rceil$. Let $G^{\prime}\subseteq G$ be a
graph, that is constructed as follows. We let $V(G^{\prime})=V(G)$, and we
include in $G^{\prime}$ all special edges of $G$. Additionally, for every
vertex $v\in L$, if $|\delta^{+}_{G}(v)|\leq 512(n-|B|)$, then we add all
regular edges that leave $v$ in $G$ to graph $G^{\prime}$, and otherwise, we
select an arbitrary subset $E^{\prime}(v)\subseteq\delta^{+}_{G}(v)$ of
$512(n-|B|)$ such edges, and include these edges in $G^{\prime}$.

Note that $G^{\prime}$ is a well-structured $n$-vertex graph, and
$(G^{\prime},A,B,\Delta,\eta,N)$ is a valid instance of the $r$-restricted
$\mathsf{RouteAndCut}$ problem. Moreover, the out-degree of every vertex $v\in
L$ is bounded by $512(n-|B|)$, and so $|E(G^{\prime})|\leq O((n-|B|)\cdot n)$.
Given the adjacency-list representation of graph $G$, graph $G^{\prime}$ can
be constructed explicitly in time $O((n-|B|)\cdot n)$.

Since $G^{\prime}\subseteq G$, any routing ${\mathcal{Q}}$ from $A$ to $B$
with congestion at most $4\eta\log N$ in $G^{\prime}$ defines a routing from
$A$ to $B$ with congestion at most $4\eta\log N$ in $G$. Assume now that we
are given a routing ${\mathcal{Q}}$ from $A$ to $B$ in $G^{\prime}$ with
congestion at most $4\eta\log N$, such that $|{\mathcal{Q}}|<\Delta$. Let
$A^{\prime}\subseteq A,B^{\prime}\subseteq B$ denote the subsets of vertices
that do not serve as endpoints of the paths in ${\mathcal{Q}}$. Assume,
additionally, that we are given a cut $(X,Y)$ in $G^{\prime}$ with
$|E_{G^{\prime}}(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$. Clearly,
$(X,Y)$ is also a cut in graph $G$. We claim that
$E_{G}(X,Y)=E_{G^{\prime}}(X,Y)$. Indeed, since $|{\mathcal{Q}}|<\Delta$, we
get that $|B^{\prime}|>|B|-\Delta$, and so $|X|\leq
n-|B^{\prime}|<n-|B|+\Delta\leq 2(n-|B|)$ (here, we have used the fact that
$\Delta\leq|A|\leq(n-|B|)$). Assume for contradiction that $E_{G}(X,Y)\neq
E_{G^{\prime}}(X,Y)$. Since $G^{\prime}\subseteq G$, there must be an edge
$e=(x,y)\in E_{G}(X,Y)$, such that $e\not\in E(G^{\prime})$. This can only
happen if $x\in L$, and graph $G^{\prime}$ contains a subset
$E^{\prime}(x)\subseteq\delta^{+}_{G}(x)$ of $512(n-|B|)$ edges. Since
$|X|\leq 2(n-|B|)$, at least $510(n-|B|)$ edges of $E^{\prime}(x)$ must lie in
$E_{G^{\prime}}(X,Y)$. Therefore, $|E_{G^{\prime}}(X,Y)|\geq 510(n-|B|)$ must
hold. However,
$|E_{G^{\prime}}(X,Y)|\leq\frac{64\Delta}{\eta\log^{4}n}+\frac{256|{\mathcal{Q}}|}{\eta}\leq
509\Delta\leq 509(n-|B|)$, a contradiction. From the above discussion, we
obtain the following claim.

######  Claim 3.10.

There is a deterministic algorithm, that, given an instance
$(G,A,B,\Delta,\eta,N)$ of the $r$-restricted $\mathsf{RouteAndCut}$ problem
(where graph $G$ is given as an adjacency list), constructs another instance
$(G^{\prime},A,B,\Delta,\eta,N)$ of the $r$-restricted $\mathsf{RouteAndCut}$
problem with $G^{\prime}\subseteq G$, such that $|E(G^{\prime})|\leq
O(n\cdot(n-|B|))$, and moreover, if $({\mathcal{Q}},(X,Y))$ is a valid
solution to instance $(G^{\prime},A,B,\Delta,\eta,N)$, then it is also a valid
solution to instance $(G,A,B,\Delta,\eta,N)$. The running time of the
algorithm is $O(n\cdot(n-|B|))$.

In our algorithms for the $\mathsf{RouteAndCut}$ problem, we will use 3.10 in
order to ensure that the number of edges in the input graph is bounded by
$O(n\cdot(n-|B|))$. We now turn to describe the MWU-based approach for solving
$r$-restricted $\mathsf{RouteAndCut}$.

###  3.5 Solving $r$-Restricted $\mathsf{RouteAndCut}$ via the Modified MWU
Framework and a Reduction to $r$-Restricted $s$-$t$-SP

In this subsection we provide a high-level description of our algorithm for
the $r$-restricted $\mathsf{RouteAndCut}$ problem, including the modified MWU
framework that we use, and a reduction to a problem that we call
$r$-restricted $s$-$t$-SP, that can be viewed as a special case of the SSSP
problem. We show that an algorithm for the $r$-restricted $s$-$t$-SP problem
implies an algorithm for the $r$-restricted $\mathsf{RouteAndCut}$ problem,
via the modified MWU framework. Lastly, we provide a simple though not very
efficient algorithm for $r$-restricted $s$-$t$-SP, that will be used as the
induction base in the proof of Theorem 3.9.

Let $(G,A,B,\Delta,\eta,N)$ be the input to the $r$-restricted
$\mathsf{RouteAndCut}$ problem instance, where $G=(L,R,E)$ is a well-
structured graph with $|V(G)|=n$, that is given as an adjancency list, $A$ and
$B$ are disjoint subsets of $V(G)$, and $N\geq n$, $\Delta\geq 1$, and
$1\leq\eta\leq\Delta$ are parameters, with $|A|,|B|\geq\Delta$. Since the
instance is $r$-restricted, $\frac{(n-|B|)\cdot\eta}{\Delta}\leq
2^{r\cdot\sqrt{\log N}}$ holds. By using the algorithm from 3.10, we convert
this instance into another instance $(G^{\prime},A,B,\Delta,\eta,N)$ of
$r$-restricted $\mathsf{RouteAndCut}$ with $|E(G^{\prime})|\leq
O(n\cdot(n-|B|))$, in time $O(n\cdot(n-|B|))$. From now on we focus on solving
instance $(G^{\prime},A,B,\Delta,\eta,N)$, and, for convenience, we denote
$G^{\prime}$ by $G$.

Recall that our goal is to compute a routing ${\mathcal{Q}}$ from $A$ to $B$,
whose congestion is bounded by $4\eta\log N$. Additionally, if
$|{\mathcal{Q}}|<\Delta$, we need to compute 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, if $A^{\prime}\subseteq A,B^{\prime}\subseteq B$ denote the subsets
of vertices that do not serve as endpoints of the paths in ${\mathcal{Q}}$,
then $A^{\prime}\subseteq X$ and $B^{\prime}\subseteq Y$ hold. Recall also
that the edges of $E_{G}(R,L)$ are called special edges, and the remaining
edges of $G$ are called regular edges. From the definition of well-structured
graphs, every vertex of $G$ is incident to at most one special edge. We start
with a simple preprocessing step.

##### A Preprocessing Step.

As a preprocessing step, we construct a maximal collection ${\mathcal{Q}}_{0}$
of disjoint paths, where every path connects a distinct vertex of $A$ to a
distinct vertex of $B$, and consists of a single regular edge. We do so by
employing a simple greedy algorithm: Start with ${\mathcal{Q}}_{0}=\emptyset$.
While there is a regular edge $e=(a,b)$ with $a\in A$ and $b\in B$, add a path
$Q=(e)$ to ${\mathcal{Q}}_{0}$, and delete $a$ and $b$ from $A$ and $B$,
respectively. Clearly, this preprocessing step can be executed in time
$O(|E(G)|)\leq O(n\cdot(n-|B|))$. If $|{\mathcal{Q}}_{0}|\geq\Delta$, then we
terminate the algorithm and return ${\mathcal{Q}}_{0}$. We assume from now on
that $|{\mathcal{Q}}_{0}|<\Delta$. Let $A_{1}\subseteq A$, $B_{1}\subseteq B$
denote the sets of vertices that do not serve as endpoints of the paths in
${\mathcal{Q}}_{0}$. Since $|{\mathcal{Q}}_{0}|<\Delta$, we get that
$|B_{1}|\geq|B|-\Delta$, and so:

$n-|B_{1}|\leq n-|B|+\Delta\leq 2(n-|B|),$ (1)

since $n-|B|\geq|A|\geq\Delta$ from the problem definition. The preprocessing
step ensures that there is no regular edge in $G$ connecting a vertex of
$A_{1}$ to a vertex of $B_{1}$, so every path connecting a vertex of $A_{1}$
to a vertex of $B_{1}$ must contain at least one special edge.

Next, we describe a modified MWU framework that will allow us to compute a
solution to the $r$-restricted $\mathsf{RouteAndCut}$ problem instance. The
modified MWU framework is designed in such a way that it reduces the
$r$-restricted $\mathsf{RouteAndCut}$ problem to a special case of SSSP, that
we call $r$-restricted $s$-$t$-SP, which seems more tractable than the general
decremental SSSP problem in directed graphs. We will then design an algorithm
for the $r$-restricted $s$-$t$-SP problem, that will allow us to obtain the
desired algorithm for $r$-restricted $\mathsf{RouteAndCut}$. The algorithm for
$r$-restricted $s$-$t$-SP will in turn rely on an algorithm for the
$(r-1)$-restricted $\mathsf{RouteAndCut}$ problem.

####  3.5.1 The Modified MWU Framework

We now describe an algorithm that is based on the modified MWU framework, but
ignore the issue of the efficient implementation of the algorithm. We address
this issue later, by reducing the problem to the $r$-restricted $s$-$t$-SP
problem.

Throughout the algorithm, we use a parameter
${\Lambda=(n-|B_{1}|)\cdot\frac{\eta\log^{5}n}{\Delta}}$. While the set
$B_{1}$ of vertices may change over the course of the algorithm, the value of
the parameter $\Lambda$ is set at the beginning of the algorithm and remains
unchanged throughout the algorithm. Our algorithm maintains an assignment
$\ell(e)\geq 0$ of _lengths_ to the edges of $G$. At the beginning of the
algorithm, we assign an initial length $\ell(e)$ to every edge $e\in E(G)$, as
follows. If $e$ is a regular edge, we set $\ell(e)=0$, and if it is a special
edge, we set $\ell(e)=\frac{1}{\Lambda}$.

As the algorithm progresses, the lengths of the special edges may grow, but
the lengths of the regular edges remain unchanged. Whenever we talk about
distances between vertices and lengths of paths, it is always with respect to
the current lengths $\ell(e)$ of edges $e\in E(G)$.

The algorithm gradually constructs a routing ${\mathcal{Q}}$ from $A_{1}$ to
$B_{1}$ in $G$, starting with ${\mathcal{Q}}=\emptyset$. It then performs at
most $\Delta$ iterations, and in every iteration, a single path $P$,
connecting some vertex $a\in A_{1}$ to some vertex $b\in B_{1}$, is added to
${\mathcal{Q}}$. We add $P$ to ${\mathcal{Q}}$, and delete $a$ from $A_{1}$
and $b$ from $B_{1}$. Additionally, we may double the lengths of some special
edges on the path $P$. Specifically, our algorithm maintains, for every
special edge $e$ of $G$, a counter $n(e)$, which, intuitively, counts the
number of paths that were added to ${\mathcal{Q}}$ that contained $e$, since
$\ell(e)$ was last doubled (or since the beginning of the algorithm, if
$\ell(e)$ was never doubled yet). At the beginning of the algorithm, we set
$n(e)=0$ for every special edge $e$. Whenever a path $P$ is added to
${\mathcal{Q}}$, we increase the counter $n(e)$ of every special edge $e\in
E(P)$. If, for any such edge $e$, the counter $n(e)$ reaches $\eta$, then we
double the length of edge $e$, and reset the counter $n(e)$ to be $0$.

#### The Oracle

At the heart of our algorithm is an _oracle_ – an algorithm that, in every
iteration, either computes a path $P$ of length at most $1$ in the current
graph $G$ connecting a vertex of $A_{1}$ to a vertex of $B_{1}$, or produces a
new assignment $\ell^{\prime}(e)$ for edges $e\in E(G)$, that we call a _cut-
witness_ , and define next. Intuitively, the cut-witness is designed in such a
way that it can be easily transformed into the desired 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, if $A^{\prime}$ and $B^{\prime}$ denote the current sets $A_{1}$
and $B_{1}$ respectively, then $A^{\prime}\subseteq X$ and
$B^{\prime}\subseteq Y$ hold. Once the oracle produces a cut-witness, the
algorithm terminates. We now define the cut-witness formally.