# An accurate and flexible analog emulation of AdEx neuron dynamics in silicon

Sebastian Billaudelle$\dagger$$\star$, Johannes Weis$\dagger$, Philipp
Dauer$\dagger$, Johannes Schemmel$\dagger$,
<EMAIL_ADDRESS>$\dagger$Kirchhoff-
Institute for Physics, Heidelberg University, Germany

###### Abstract

Analog neuromorphic hardware promises fast brain emulation on the one hand and
an efficient implementation of novel, brain-inspired computing paradigms on
the other. Bridging this spectrum requires flexibly configurable circuits with
reliable and reproducible dynamics fostered by an accurate implementation of
the targeted neuron and synapse models. This manuscript presents the analog
neuron circuits of the mixed-signal accelerated neuromorphic system
BrainScaleS-2. They are capable of flexibly and accurately emulating the
adaptive exponential leaky integrate-and-fire (AdEx) model equations in
combination with both current- and conductance-based synapses, as demonstrated
by precisely replicating a wide range of complex neuronal dynamics and firing
patterns.

###### Index Terms:

analog neuromorphic, AdEx, silicon neuron

##  I Introduction

Aparameter storagecadcppuanalog network core Y1.0e0]ptevent
handlingY1.0e0]ptI/OY1.0e0]ptconfig.memorycontrol.synapse arrayneuronsBC
Figure 1: (A) Photograph of a BrainScaleS-2 ASIC. (B) Block-level schematic of
the neuromorphic system. (C) Block-level schematic of the silicon neuron.

Spiking neuron models attempt to replicate the time-continuous dynamics and
the event-based, asynchronous communication scheme of their archetype.
Building on the simpler leaky integrate-and-fire (LIF) equation, the AdEx
model captures these fundamental properties and can reproduce many of the
dynamics and firing patterns found in electrophysiological recordings of
biological neurons [1]. It describes the dynamics of the membrane potential
$V$ as

$\displaystyle C\dfrac{\operatorname{d\\!}{}V}{\operatorname{d\\!}{t}}$
$\displaystyle=-g_{\text{l}}\left(V-E_{\text{l}}\right)\,+\,g_{\text{l}}\Delta_{\text{T}}\operatorname{e}^{\frac{V-V_{\text{T}}}{\Delta_{\text{T}}}}\,-\,w\,+\,I\,,$
(1)

with membrane capacitance $C$, leak potential $E_{\text{l}}$, leak conductance
$g_{\text{l}}$, soft threshold $V_{\text{T}}$, and exponential slope
$\Delta_{\text{T}}$. The dynamics of the adaptation current $w$ are governed
by

$\displaystyle\tau_{\text{w}}\dfrac{\operatorname{d\\!}{}w}{\operatorname{d\\!}{t}}$
$\displaystyle=a\left(V-E_{l}\right)-w\,,$ (2)

with time constant $\tau_{\text{w}}$ and subthreshold adaptation strength $a$.
The time-continuous dynamics are accompanied by spike-triggered jump
conditions $V\rightarrow V_{\text{r}}$ and $w\rightarrow w+b$.

Synaptic interaction is typically modeled by weighting and accumulating the
presynaptic spike trains of each synapse $i$,
$S_{i}(t)=\sum_{j}\delta(t-t_{j})$, and by convolving them with an interaction
kernel, typically an exponential decay
$s(t)=\sum_{i}w_{i}S_{i}(t)\circledast\exp(t/\tau_{\text{syn}})$. This
integrator trace is then translated into a current onto the membrane either
directly (_current-based_) or by modulating a conductance pulling the membrane
towards a synaptic reversal potential (_conductance-based_):

$\displaystyle I_{\text{cuba}}=\hat{I}\cdot s(t)\,,\quad\text{or}\quad
I_{\text{coba}}=\hat{g}\cdot s(t)\cdot\left[E_{\text{syn}}-V\right]\,.$ (3)

The AdEx equations and other complex neuron models have inspired a plethora of
analog neuromorphic implementations [2, 3, 4, 5, 6] and also lay the
foundation for the silicon neuron presented in this manuscript. The discussed
silicon neuron can accurately reproduce the original model dynamics and can be
configured for a wide range of parameterizations.

The neuron circuits represent one of the central components of the analog core
of BrainScaleS-2 (Figure 1), a mixed-signal neuromorphic system emulating
neuronal and synaptic dynamics on 1000-fold accelerated time scales compared
to the biological nervous system. The silicon neurons are embedded into the
rich infrastructure provided by the neuromorphic ASIC (Figure 1). They receive
weighted stimuli via the synapse array and relay their output spikes to the
chip-internal event routing fabric. While partially controlled and interfaced
through full-custom digital backend logic (Figure 1), the neuronal dynamics
are realized by analog circuits.

##  II Silicon Implementation

The design can be separated into multiple functional blocks mainly
corresponding to the individual terms of the model equations. The circuit is
implemented in a $65\text{\,}\mathrm{nm}$ bulk complementary metal-oxide-
semiconductor (CMOS) technology and occupies an active silicon area of
approximately $2575\text{\,}{\mathrm{\SIUnitSymbolMicro m}}^{2}$.

###  II-A Bulk-driven OTA as a building block

The mostly linear nature of the differential equations behind the model
dynamics emphasizes the need for an area- and energy-efficient, widely linear
component, mainly to translate voltages into proportional currents. For that
purpose, preceding silicon neurons have often already relied on operational
transconductance amplifiers (OTAs) [7, 6]. Saturation effects and the limited
linear range of standard OTA designs, however, can dramatically distort the
underlying dynamics when compared to the original model equations. The
presented circuits address this issue by relying on a bulk-driven differential
pair (M1, M2) to linearize the characteristics of the OTA (Figure 2). Bulk-
driven circuits exploit the body effect to modulate a transistor’s drain
current [8]. In the present case, we make use of the reduced transconductance
$g_{\text{mb}}\ll g_{\text{m}}$ to increase the linear input range of the OTA
(Figure 2), lifting the requirement for more complex and less area- or energy-
efficient linearization techniques but requiring careful biasing and
verification to always maintain reverse biased body diodes. Depending on the
exact, application-specific dimensioning, the discussed circuit exhibits a
footprint down to less than $10\times 10\text{\,}{\mathrm{\SIUnitSymbolMicro
m}}^{2}$, despite the requirement for isolated and thus spatially separated
n-wells for the two transistors of the differential pair. It serves with only
slight modifications to the specific instantiation as a common building block
for the silicon neuron, e.g. realizing the leak conductance of the membrane
dynamics (Equation 1).

A B Figure 2: (A) Bulk-driven OTA serving as a building block for the silicon
neuron (simplified schematic). (B) Small signal transconductance measured for
different bias currents.

###  II-B Adaptation

The adaptation state variable $w$ (Equation 2) also resembles leaky integrator
dynamics. While taking the form of a current in the model equations, it is in
our silicon neuron represented as a voltage $V_{\text{w}}$. The core dynamics
are, hence, implemented through a low-pass filter, directly relying on a
capacitor and the bulk-driven OTA as a pseudo-conductance (Figure 3), allowing
to tune the adaptation time constant through its bias (Figure 3). We fitted
OTA2 with a second, approximately twelve-fold stronger output stage to
repurpose the circuit to also generate the adaptation current
$I_{\text{w}}=g_{\text{w}}\left(I_{\text{b}}^{\tau}\right)\left(V_{\text{ref}}-V_{\text{w}}\right)$
directed onto the membrane.

The adaptation state is driven by the membrane-dependent subthreshold
contributions on one hand and spike-triggered increments on the other. The
former are realized through OTA1, whereby the coupling strength
$g_{\text{a}}\left(I_{\text{b}}^{\text{a}}\right)$ is controlled via the
respective bias current (Figure 3). The time-continuous dynamics of the
adaptation current hence result as

$\displaystyle\tau_{\text{w}}\dfrac{\operatorname{d\\!}{}I_{\text{w}}}{\operatorname{d\\!}{t}}$
$\displaystyle=-\tau_{\text{w}}g_{\text{w}}\dfrac{\operatorname{d\\!}{}V_{\text{w}}}{\operatorname{d\\!}{t}}=\pm\underbrace{g_{\text{a}}\frac{g_{\text{w}}}{g_{\tau}}}_{\equiv
a}\cdot\left(V_{\text{m}}-E_{\text{l}}^{\text{adapt}}\right)-I_{\text{w}}\,,$
(4)

with $\tau_{\text{w}}\left(I_{\text{b}}^{\tau}\right)\equiv
C_{\text{w}}/g_{\tau}\left(I_{\text{b}}^{\tau}\right)$. These dynamics are
augmented by spike-triggered in- or decrements of $V_{\text{w}}$ resulting
from short current pulses $I_{\text{b}}$ with configurable width and
amplitude.

A B C Figure 3: (A) Bulk-driven OTA serving as a building block for the
silicon neuron (simplified schematic). (B) Small signal transconductance
measured for different bias currents. (C) Schematic of the adaptation circuit.
(D) Trajectory of the adaptation voltage after clamping and releasing from a
fixed potential, measured for different bias currents. (E) Transient response
of a membrane to a step current measured for different subthreshold adaptation
strengths.

###  II-C Exponential feedback current

The exponential term is in its core implemented through the characteristics of
a single metal-oxide-semiconductor field-effect transistor (MOSFET) biased in
weak inversion (Figure 4, M4). Its gate-to-source voltage is derived from the
membrane via an OTA and a subsequent current-to-voltage conversion implemented
straight-forwardly through a long-channeled transistor (M3) biased to operate
in its linear region and thus acting as a resistor with on-resistance
$r_{\text{conv}}$. This compact conversion circuit allows tuning the
exponential current’s onset and slope (Figure 4, Figure 4):

$\displaystyle I_{\text{exp}}(V_{\text{m}})$
$\displaystyle=I_{0}\cdot\exp\left(\frac{8\cdot
g_{\text{ota}}\cdot\left[V_{\text{m}}-V_{\text{exp}}\right]}{n\cdot
V_{\text{T}}/r_{\text{conv}}}\right)\,.$ (5)

This current is mirrored onto the membrane and can be gated either to disable
the whole circuit or to “pause” the strong exponential feedback during the
neuron’s refractory period. The current mirror formed by M1 and M2 rectifies
the output current of OTA1 and, hence, effectively powers down the second half
of the circuit for membrane potentials significantly below $V_{\text{T}}$.

A B C Figure 4: (A) Bulk-driven OTA serving as a building block for the
silicon neuron (simplified schematic). (B) Small signal transconductance
measured for different bias currents. (C) Schematic of the adaptation circuit.
(D) Trajectory of the adaptation voltage after clamping and releasing from a
fixed potential, measured for different bias currents. (E) Transient response
of a membrane to a step current measured for different subthreshold adaptation
strengths. (F) Exponential term. (G) & (H) The exponential current is
correctly reproduced across three orders of magnitude and can be parameterized
via the reference potential and the OTA’s bias. Saturation of the OTA, the
current-to-voltage conversion, and the output stage limits $I_{\text{exp}}$
but – due to the overall fast transients – does not significantly impact spike
timing.

###  II-D Emulating current- and conductance-based synapses

The synaptic integrator circuits (LABEL:fig:synin-schematic) represent the
interface between the synapse array and the neuron’s membrane circuits. They
integrate current pulses from their associated column of synapses [9] and
modulate the membrane in analogy to Equation 3. Here, the low-pass filter
directly exploits the synaptic line’s capacitance, which can optionally be
augmented with a dedicated capacitor. The conductance (in LABEL:fig:synin-
schematic schematically drawn as a variable resistor) is realized through
multiple series-connected p-channel MOSFETs. They are biased in weak inversion
to a constant gate-to-source voltage, similar to the predecessor circuit [6].

OTA1 derives a current $I_{\text{synin}}=g_{1}\cdot\Delta V_{\text{syn}}$
based on the deflection of the integrator voltage, directly implementing a
_current-based_ output. In that process, offsets can be compensated by tuning
the voltage drop of the two source followers (M1, M2) via their bias currents.
_Conductance-based_ synapses (LABEL:fig:synin-coba) are realized via an
additional feedback path: OTA2 can modulate the bias current of OTA1 based on
the membrane potential such that

$\displaystyle g_{1}$ $\displaystyle\propto
g_{2}\cdot\left(\smash[b]{\underbrace{\hat{E}_{\text{syn}}+I_{\text{b}}^{\text{cuba}}/g_{2}}_{\equiv
E_{\text{syn}}}}-V_{\text{m}}\right)\vphantom{\left(\underbrace{\hat{E}}_{E}\right.}\,,$
(6)

where $g_{1}$ is assumed to be approximately proportional to the applied bias
current. Mixing the static bias current with an additional, modulated
component allows to create a “virtual” reversal potential $E_{\text{syn}}$. In
the excitatory case, the latter usually extends far beyond the threshold
voltage and thus falls outside the membrane’s dynamic range. Our design
decouples the true zero crossing – and with it the linear range – of OTA2 from
that normally never reached reversal potential.

##  III Results

TABLE I: Parameter ranges and variability across 128 neurons. parameter |  | minimum | maximum | unit
---|---|---|---|---
membrane time constant | $\tau_{\text{m}}$ | $0.6\pm 0.2$ | $915\pm 140$ | $\mathrm{\SIUnitSymbolMicro s}$
leak potential | $E_{\text{l}}$ | 0.0 | 1.0 | $\mathrm{V}$
firing threshold | $V_{\text{l}}$ | 0.2 | 1.2 | $\mathrm{V}$
stimulus current | $I_{\text{stim}}$ | 0.0 | $121\pm 14$ | $\mathrm{nA}$
synaptic time constant | $\tau_{\text{syn}}$ | $0.29\pm 0.03$ | $538\pm 98$ | $\mathrm{\SIUnitSymbolMicro s}$
synaptic peak current | $I_{\text{syn}}$ | $0.033\pm 0.003$ | $1.15\pm 0.03$ | $\mathrm{\SIUnitSymbolMicro A}$
adaptation time constant | $\tau_{\text{w}}$ | $22\pm 3$ | $853\pm 117$ | $\mathrm{\SIUnitSymbolMicro s}$
subthreshold adaptation | $\mathinner{\\!\left\lvert a\right\rvert}$ | $30\pm 4$ | $1065\pm 114$ | $\mathrm{\SIUnitSymbolMicro S}$
spike-triggered adapt. | $\mathinner{\\!\left\lvert b\right\rvert}$ | 0 | $\infty$ | $\mathrm{\SIUnitSymbolMicro A}$
exponential slope | $\Delta_{\text{T}}$ | $13\pm 2$ |  $>$$91\pm 46$ | $\mathrm{mV}$

The neuron circuit’s dynamics can be tuned via 16 analog bias currents and 8
voltages individually provided for each neuron instance and a set of digital
controls ($40\text{\,}\mathrm{bit}$ of local static random-access memory
(SRAM)) to en- or disable parts of the circuit. This large configuration space
allows the flexible emulation of a wide range of model dynamics. Table I
summarizes the parameter ranges achieved by the neuron design, measured across
128 neurons. The effective parameter ranges can in many cases be further
extended by selecting a reduced membrane capacitance, here configured for its
maximum value of approximately $2.47\text{\,}\mathrm{pF}$.

With each neuron instance receiving an individual set of analog references
generated by the on-chip parameter storage [10], one may not only precisely
tune the operating points to certain target dynamics but can also compensate
for process corner effects as well as mismatch-induced fixed-pattern
variability across neurons, a process we refer to as _calibration_. The
flexible parameterization and calibration allows to configure the neuron
circuits for a wide range of operating points. In the following, we will
demonstrate the reliability and accuracy of the silicon neuron and for that
purpose, in each case, discuss the dynamics of a population of $128$
calibrated neurons.

###  III-A LIF neuron dynamics

Calibrating the neuron circuits to a leak-over-threshold regime exhibits well-
matching dynamics (Figure 5) and narrow inter-spike interval (ISI)
distributions (Figure 5). The ISIs furthermore closely correspond to those
predicted by evaluating the original model equations based on the calibration
targets, here measured for membrane time constants spanning two full orders of
magnitude (Figure 5).

A calibration of the synaptic input circuits, namely of $\tau_{\text{syn}}$,
their effective amplitudes, and offsets, yields similarly well-matching
postsynaptic currents. This results in homogeneous postsynaptic potential
(PSP) trajectories (Figure 5), leaving the membrane’s resting potential mostly
unaffected (Figure 5) and yielding closely matching amplitudes (Figure 5).

A B C D E F Figure 5: (A) Bulk-driven OTA serving as a building block for the
silicon neuron (simplified schematic). (B) Small signal transconductance
measured for different bias currents. (C) Schematic of the adaptation circuit.
(D) Trajectory of the adaptation voltage after clamping and releasing from a
fixed potential, measured for different bias currents. (E) Transient response
of a membrane to a step current measured for different subthreshold adaptation
strengths. (F) Exponential term. (G) & (H) The exponential current is
correctly reproduced across three orders of magnitude and can be parameterized
via the reference potential and the OTA’s bias. Saturation of the OTA, the
current-to-voltage conversion, and the output stage limits $I_{\text{exp}}$
but – due to the overall fast transients – does not significantly impact spike
timing. (I) Traces of 128 neurons calibrated for leak-over-threshold dynamics
(J) and their ISIs. (K) ISIs for different choices of $\tau_{\text{m}}$ and
comparison to predicted values. (L) PSP traces of 128 neurons and
distributions of (M) their baselines (N) and amplitudes.

###  III-B AdEx firing patterns

We benchmarked the full AdEx circuits by seeking to reproduce the different
firing patterns discussed by [1] [1]. With only few exceptions, we relied on
the originally published parameter sets and employed fully automated
calibration routines to find suitable circuit configurations corresponding to
those target dynamics. Figure 6 shows measured membrane and adaptation state
traces for the first of 128 neurons. These rich dynamics all emerge as a
response to a constant step current and differentiate themselves only in the
neurons’ parameterizations. All calibrated 128 neurons could – with only
slight deviations in the exact spike times and counts – reproduce the desired
firing patterns.

A B C D E F Figure 6: Membrane and adaptation state recordings as well as the
reconstructed phase plane trajectory measured for a silicon neuron
parameterized for various AdEx firing patterns. (A) Bulk-driven OTA serving as
a building block for the silicon neuron (simplified schematic). (B) Small
signal transconductance measured for different bias currents. (C) Schematic of
the adaptation circuit. (D) Trajectory of the adaptation voltage after
clamping and releasing from a fixed potential, measured for different bias
currents. (E) Transient response of a membrane to a step current measured for
different subthreshold adaptation strengths. (F) Exponential term. (G) & (H)
The exponential current is correctly reproduced across three orders of
magnitude and can be parameterized via the reference potential and the OTA’s
bias. Saturation of the OTA, the current-to-voltage conversion, and the output
stage limits $I_{\text{exp}}$ but – due to the overall fast transients – does
not significantly impact spike timing. (I) Traces of 128 neurons calibrated
for leak-over-threshold dynamics (J) and their ISIs. (K) ISIs for different
choices of $\tau_{\text{m}}$ and comparison to predicted values. (L) PSP
traces of 128 neurons and distributions of (M) their baselines (N) and
amplitudes. (O) – (T)  _Adaptation_ , _delayed accelerating_ , _initial burst_
, _regular bursting_ , _delayed regular bursting_ , and _transient spiking_.

##  IV Discussion

The circuits discussed in this manuscript faithfully emulate the AdEx model
equations and synaptic interaction. They can be precisely calibrated to a wide
range of operating points and capture the model dynamics with unprecedented
accuracy. Being part of the mixed-signal accelerated neuromorphic system
BrainScaleS-2, they have proven themselves in a wide range of experimental
studies ranging from the emulation of structured neurons to the machine-
learning inspired training of spiking neural networks [11, 12].

## Acknowledgements

We thank A. Grübl, G. Kiene, Y. Stradmann, the Electronic Vision(s) group, and
all others involved for their contributions.

This work has received funding from the European Union research and innovation
funding H2020 945539 (HBP SGA3), DFG project EXC 2181/1 – 390900948
(STRUCTURES), the Helmholtz Association project SO-092 (ACA), and the Manfred
Stärk Foundation.

## References

  * [1] Richard Naud et al. “Firing patterns in the adaptive exponential integrate-and-fire model” In _Biological cybernetics_ 99.4 Springer, 2008, pp. 335–347
  * [2] Jayawan HB Wijekoon and Piotr Dudek “Integrated circuit implementation of a cortical neuron” In _2008 IEEE International Symposium on Circuits and Systems_ , 2008, pp. 1784–1787 IEEE
  * [3] Fopefolu Folowosele et al. “A switched capacitor implementation of the generalized linear integrate-and-fire neuron” In _2009 IEEE International Symposium on Circuits and Systems_ , 2009, pp. 2149–2152 IEEE
  * [4] André Van Schaik et al. “A log-domain implementation of the Mihalas-Niebur neuron model” In _2010 IEEE International Symposium on Circuits and Systems_ , 2010, pp. 4249–4252 IEEE
  * [5] Elisabetta Chicca et al. “Neuromorphic electronic circuits for building autonomous cognitive systems” In _Proceedings of the IEEE_ 102.9 IEEE, 2014, pp. 1367–1388
  * [6] Syed Ahmed Aamir et al. “A mixed-signal structured AdEx neuron for accelerated neuromorphic cores” In _IEEE transactions on biomedical circuits and systems_ 12.5 IEEE, 2018, pp. 1027–1037
  * [7] Sebastian Millner et al. “A VLSI implementation of the adaptive exponential integrate-and-fire neuron model” In _Advances in Neural Information Processing Systems_ 23, 2010
  * [8] Fabian Khateb et al. “Utilizing the bulk-driven technique in analog circuit design” In _13th IEEE Symposium on Design and Diagnostics of Electronic Circuits and Systems_ , 2010, pp. 16–19 IEEE
  * [9] Simon Friedmann et al. “Demonstrating hybrid learning in a flexible neuromorphic hardware system” In _IEEE transactions on biomedical circuits and systems_ 11.1 IEEE, 2016, pp. 128–142
  * [10] Matthias Hock et al. “An analog dynamic memory array for neuromorphic hardware” In _2013 European Conference on Circuit Theory and Design (ECCTD)_ , 2013, pp. 1–4 IEEE
  * [11] Sebastian Billaudelle et al. “Versatile emulation of spiking neural networks on an accelerated neuromorphic substrate” In _2020 IEEE International Symposium on Circuits and Systems_ , 2020, pp. 1–5 IEEE
  * [12] Christian Pehle et al. “The BrainScaleS-2 Accelerated Neuromorphic System With Hybrid Plasticity” In _Frontiers in Neuroscience_ 16, 2022 DOI: 10.3389/fnins.2022.795876


# Incremental Approximate Maximum Flow in $m^{1/2+o(1)}$ update time

Gramoz Goranci Institute for Theoretical Studies, ETH Zurich, Switzerland.
This project is supported by Dr. Max Rössler, the Walter Haefner Foundation
and the ETH Zürich Foundation. Monika Henzinger Faculty of Computer Science,
University of Vienna, Austria. See funding information in the acknowledgement
section.

###### Abstract

We show an $(1+\epsilon)$-approximation algorithm for maintaining maximum
$s$-$t$ flow under $m$ edge insertions in $m^{1/2+o(1)}\epsilon^{-1/2}$
amortized update time for directed, unweighted graphs. This constitutes the
first sublinear dynamic maximum flow algorithm in general sparse graphs with
arbitrarily good approximation guarantee.

##  1 Introduction

The maximum flow problem is one of the cornerstone and the most studied
problem in combinatorial optimization. It is often used as subroutine for
solving other prominent graph problems (e.g., Gomory-Hu Trees [8], Sparsest
Cut [17]), performing divide-and-conquer on graphs and has found several
applications across many areas including computer vision, clustering and
scientific computing. Designing fast maximum flow algorithms has been an
active area of research for decades, with recent advances making tremendous
progress towards the quest of designing a near-linear time algorithm [5, 22,
19, 16, 21, 20, 23, 18, 3].

Recently, we have witnessed a growing interest in designing dynamic algorithms
for computing maximum flows in dynamically changing graphs [15, 4, 1, 6, 10,
9, 2]. Despite this, the current best-known algorithms either incur super-
constant approximation factors [9, 2] or achieve competitive update times only
for sufficiently dense graphs [1]. Moreover, all previous works on dynamic
flows are restricted to undirected graphs. From a (conditional) lower bound
perspective, for any $\delta>0$, it is known [6] that no algorithm can exactly
maintain maximum flow in $O(m^{1-\delta})$ amortized time per operation, even
when restricted to algorithms that support edge insertions, unless the OMv
conjecture [12] is false. This suggests that approximation is necessary to
achieve sublinear running times for general sparse graphs.

In this paper, we show a simple generic algorithmic framework for maintaining
approximate maximum flows under edge insertions.

######  Theorem 1.1.

Let $G=(V,E)$ be an initially empty, directed, unweighted $n$-vertex graph,
$s$ and $t$ be any two vertices, and $\epsilon>0$, $\mu\in[0,n]$ be two
parameters. If there is

  1. (a)

an incremental algorithm $\textup{{IncBMF}}(G,s,t,\mu)$ for inserting $m$
edges and maintaining $s$-$t$ maximum flow whose value is bounded by $\mu$ in
total update time $t_{\textrm{total}}(m,n,\mu)$ and $q(m,n)$ query time, and

  2. (b)

a static algorithm for computing exact $s$-$t$ maximum flow in an $n$-vertex,
$m^{\prime}$-edge graph in $t_{\textrm{static}}(m^{\prime},n)$ time, where
$m^{\prime}\leq m$,

then we can design an incremental algorithm for maintaining a
$(1+\epsilon)$-approximate $s$-$t$ maximum flow under $m$ edge insertions in

$\frac{t_{\textrm{total}}(m,n,\mu+1)}{m}+\frac{t_{\textrm{static}}(m,n)}{\epsilon\mu}+q(m,n)$

amortized update time and $q(m,n)$ query time.

For maintaining exact maximum flows whose value is bounded by $\mu$, we
slightly adapt an incremental version of the Ford-Fulkerson [7] algorithm,
which was initially observed by Heniznger [13] and later by Gupta and Khan
[10] (cf. Theorem 4.2). This gives an incremental algorithm with $O(m\mu)$
total update time and $O(1)$ query time. The recent breakthrough result due to
Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva [3] (cf. Theorem 2.3)
shows a static exact maximum flow algorithm that runs in $m^{1+o(1)}$ time.
Plugging these bounds in Theorem 1.1 and choosing
$\mu=m^{1/2+o(1)}\epsilon^{-1/2}$ yields the main result of this paper, which
we summarize in the theorem below.

######  Theorem 1.2.

Given an initially empty, directed, unweighted graph $G=(V,E)$, any two
vertices $s$ and $t$ in $V$, and any $\epsilon>0$, there is an incremental
algorithm that maintains a $(1+\epsilon)$-approximate maximum $s$-$t$ flow in
$G$ under $m$ edge insertions in $m^{1/2+o(1)}\epsilon^{-1/2}$ amortized
update time. The algorithm supports queries about the value of the maintained
flow in $O(1)$ time.

We believe that our approach to dynamic flows may serve as the basis for
designing new fully-dynamic maximum flow algorithms with competitive
approximation ratio.

##  2 Preliminaries

In the following we settle some basic notation, as well as review definitions
and algorithms for computing flows on graphs.

### Maximum Flow.

Let $G=(V,E)$ be a directed, unweighted graph with $n$ vertices and $m$ edges,
let $s\in V$ be a _source_ vertex and let $t\in V$ be a _target_ vertex. An
_flow_ from $s$ to $t$ in $G$ is a function $f:E\rightarrow\mathbb{R}^{+}$
that maps each edge to a non-negative real number; the value $f(e)$ represents
the amount of flow sent along $e$. A flow must satisfy the following
properties: (i) for each $e\in E$, we have $f(e)\leq 1$, known as _capacity
constraints_ , and (ii) for each $v\in V\setminus\\{s,t\\}$, $\sum_{(u,v)\in
E}f(u,v)=\sum_{(v,u)}f(v,u)$, known as _conservation constraints_. The _value_
of a flow $f$ is the amount of flow leaving the source $s$ minus the amount
flow flow entering $s$, i.e., $v(f)=\sum_{(s,u)\in E}f(s,u)-\sum_{(u,s)\in
E}f(u,s)$. In the _maximum $s$-$t$ flow_ problem, the goal is to find a flow
$f$ with the largest $v(f)$, called the _m_ aximum $s$-$t$ flow . Let
$F^{*}=\max\\{v(f)\mid f\text{ is a flow in }G\\}$. Note that while $F^{*}$ is
unique, there might be multiple maximum $s$-$t$ flows attaining $F^{*}$.

### Residual graph and Augmenting Paths.

Given a directed, unweighted graph $G=(V,E)$, and a flow $f$ from $s$ to $t$
in $G$, we let $G_{f}=(V,E_{f})$ be the _residual graph_ of $G$ with respect
to $f$, where $E_{f}$ contains all edges of $E$, except that their direction
is reversed if $f(e)=1$. An edge whose direction in $G_{f}$ is reversed is
referred to as a _backward_ edge. Otherwise, the edge is a _forward_ edge. An
augmenting path $P$ from $s$ to $t$ in $G$ is a simple directed path from $s$
to $t$ in $G_{f}$. We next review a powerful result relating the residual
graphs and optimal flows.

######  Lemma 2.1 ([7]).

If there is no directed path from $s$ to $t$ in the residual graph $G_{f}$,
then the flow $f$ is a maximum $s$-$t$ flow.

Another useful fact is giving in the lemma below.

######  Fact 2.2.

If there exists a directed path $P$ from $s$ to $t$ in $G_{f}$, pushing flow
along $P$ in $G$ increases the value of the flow $f$ by at exactly one.

### Exact Maximum Flow in Directed Graphs.

Our incremental approximate algorithm heavily relies on the ability to compute
a maximum $s$-$t$ flow quickly. Hence, we use the current breakthrough result
[3] that achieves an exact, almost-linear algorithm for the maximum flow
problem on directed graphs.111The algorithm extends to graphs with
polynomially bound weights, but for the purposes of this paper and simplifying
the presentation, we only state the unweighted version of this result

######  Theorem 2.3 ([3]).

For any directed, unweighted graph $G=(V,E)$ and any two vertices $s$ and $t$,
there is an algorithm that computes an _exact_ maximum $s$-$t$ flow in $G$ in
$m^{1+o(1)}$ time.

### Approximate Maximum Flow.

To measure the quality of approximate maximum flows, we will use the notion of
$\alpha$-approximations, which indicates that the value of the current flow
solution is at least $1/\alpha$ of the optimum value. In other words, a flow
$f$ is $\alpha$-approximate if $F:=v(f)\geq\frac{1}{\alpha}F^{*}$.

##  3 A framework for Incremental Approximate Maximum Flow

In this section we show a simple generic algorithmic framework for maintaining
a $(1+\epsilon)$-approximate maximum $s$-$t$ flow under edge insertions, i.e.,
prove Theorem 1.1. Our construction is based on two important components: (i)
incrementally maintaining maximum $s$-$t$ flows whose value is upper bounded
by some parameter $\mu$ (one should think of $\mu$ being small relative to the
size of the network) and (ii) performing periodical rebuilds whenever the
maximum $s$-$t$ flow of the current flow is larger than the parameter $\mu$.
This is a common approach in dynamic algorithms and was used e.g., by Gupta
and Peng [11] in their dynamic algorithm for maintaining approximate
matchings. We next further elaborate on the precise requirements of both
components, and discuss how they lead to our algorithm.

To implement component (i), given a directed, unweighted graph $n$-vertex,
$m$-edge graph $G$, any two vertices $s$, $t$, and a parameter $\mu\in[0,n]$,
the goal is to construct a data structure denoted by
$\textsc{IncBMF}(G,s,t,\mu)$, or simply IncBMF, that supports the following
operations

  * •

Initialize$(G,s,t,\mu)$: Initializes the data structure.

  * •

Insert$(u,v)$: Insert the edge $(u,v)$ to $G$.

  * •

MaxFlow$(s,t)$: Return the value of the maximum $s$-$t$ flow in the current
graph $G$ if this value is smaller than $\mu$.

Ideally, we would like that $\textsc{IncBMF}(G,s,t,\mu)$ supports edge
insertions in amortized time proportional to the parameter $\mu$, and queries
in constant time. This would alone lead to an efficient incremental maximum
flow algorithm whenever the current flow value is bounded by $\mu$.

When the maximum flow is large (i.e., component (ii)), we can make use of the
_stability_ of maximum flow and periodically invoke a fast static algorithm.
Concretely, first note that the value of the maximum $s$-$t$ flow changes by
at most one per insertion. Therefore, if we have a large flow that is close to
the maximum one, it will remain close to the maximum flow over a large number
of updates. This naturally leads to the following simple but powerful
approach: compute a flow at a certain time in the update sequence and do
nothing for a certain number of updates as long as the flow is a good
approximation to the maximum flow. This idea together with the data structure
$\textsc{IncBMF}(G,s,t,\mu)$ yields an incremental algorithm for approximating
$s$-$t$ maximum flow, which we formally describe below.

Given a directed, unweighted graph $G=(V,E)$, any two vertices $s$, $t$, and
two parameters $\epsilon>0,\mu\in[0,n]$, our data structure maintains:

  * •

a flow estimate $F$ to the maximum $s$-$t$ flow $F^{*}$,

  * •

a counter $\tau$ indicating the number of operations since the last rebuild,

  * •

an incremental algorithm IncBMF for maintaining graphs with the maximum flow
bounded by some parameter $(\mu+1)$.

Initially, $G$ is an empty graph, $F\leftarrow 0$, $\tau\leftarrow 0$, and we
invoke the operation $\textsc{Initialize}(G,s,t,\mu+1)$ of IncBMF. Upon
insertion of an edge $(u,v)$ to $G$, we query IncBMF to determine whether the
$s$-$t$ maximum flow in the current graph is at most $\mu$. If so, we pass the
edge insertion to the IncBMF data structure and update $F$ accordingly.

On the other hand, if the current maximum $s$-$t$ flow is larger than $\mu$
(and our algorithm always correctly detects this since IncBMF run with the
parameter $(\mu+1)$ returns the correct answer), we increment $\tau$, which
counts the number of insertions since the last reset of $\tau$ that fall into
this case. If $\tau\geq\epsilon\mu$, we compute an exact maximum flow $F^{*}$
for the current graph from scratch using a static algorithm, update $F$ using
the value of $F^{*}$ and set $\tau=0$. We call such a step a _rebuild_ step.
Observe that since we are in the insertions-only setting, once a maximum flow
is larger than $\mu$, it remains larger than that value. Finally, to answer a
query about the maximum $s$-$t$ flow, we return $F$ as an estimate. These
procedures are summarized in Algorithm 1.

1

2Procedure  _Initialize(_$G=(V,E)$ , $s$, $t$, $\epsilon$, $\mu$_)_

3 Set $E\leftarrow 0$ and $F\leftarrow 0$

4 Invoke $\textsc{IncBMF}.\textsc{Initialize}(G,s,t,\mu+1)$

5

6Procedure  _Insert(_$u,v$_)_

7 $E\leftarrow E\cup\\{(u,v)\\}$

8 if  _$\textsc{IncBMF}.\textsc{MaxFlow}(s,t)\leq\mu$_ then

9 Invoke $\textsc{IncBMF}.\textsc{Insert}(u,v)$

10 Set $F\leftarrow\textsc{IncBMF}.\textsc{MaxFlow}(s,t)$

11 else

12

13 Set $\tau\leftarrow\tau+1$

14 if  _$\tau\geq\epsilon\mu$_ then

15 Compute an $s$-$t$ maximum flow in $G$ using a static algorithm

16 Set $F$ to be the value of the flow computed in the previous step

17 Set $\tau\leftarrow 0$

18

19

20

21

22Procedure  _MaxFlow(_$s,t$_)_

23 return $F$

24

Algorithm 1 Incremental Approximate Maximum Flow (IncApproxMF)

######  Theorem 3.1 (Restatement of Theorem 1.1).

Let $G=(V,E)$ be an initially empty, directed, unweighted $n$-vertex graph,
$s$ and $t$ be any two vertices, and $\epsilon>0$, $\mu\in[0,n]$ be two
parameters. If there is

  1. (a)

an incremental algorithm $\textup{{IncBMF}}(G,s,t,\mu)$ for inserting $m$
edges and maintaining $s$-$t$ maximum flow whose value is bounded by $\mu$ in
total update time $t_{\textrm{total}}(m,n,\mu)$ and $q(m,n)$ query time, and

  2. (b)

a static algorithm for computing exact $s$-$t$ maximum flow in an $n$-vertex,
$m^{\prime}$-edge graph in $t_{\textrm{static}}(m^{\prime},n)$ time, where
$m^{\prime}\leq m$,

then we can design an incremental algorithm for maintaining a
$(1+\epsilon)$-approximate $s$-$t$ maximum flow under $m$ edge insertions in

$\frac{t_{\textrm{total}}(m,n,\mu+1)}{m}+\frac{t_{\textrm{static}}(m,n)}{\epsilon\mu}+q(m,n)$

amortized update time and $q(m,n)$ query time.

###### Proof.

We first prove the correctness of the algorithm. Let $G$ be the current graph
and let $F$ be the estimate maintained by the algorithm to the value of the
maximum $s$-$t$ flow $F^{*}$ in $G$. We will show that $F$ is an
$(1+\epsilon)$-approximation to $F^{*}$. To this end, we distinguish the
following three cases. (1) If $F^{*}\leq\mu$, then by assumption of the
theorem, the data structure IncBMFensures that $F=F^{*}$ and thus our claim
trivially holds. (2) If $F^{*}=\mu+1$, the call
$\textsc{IncBMF}.\textsc{MaxFlow}(s,t)$ returns the value $\mu+1$ and, thus,
the algorithm reaches the else-case for the first time (here we slightly abuse
the notation and denote this as a _rebuild_ step).

(3) If $F^{*}>\mu+1$, then this is not the first time that the algorithm
reaches the else-case and, thus, there was a prior rebuild. Note that $F$
corresponded to the value of some $s$-$t$ maximum flow at the last prior
rebuild. This in turn implies that $F$ must be larger than $\mu$. Let
$F^{*}_{0}$ be the value of the maximum $s$-$t$ flow of the graph at that
rebuild. Since each edge insertions can increase the value of the maximum flow
by at most $1$ and we recompute a new maximum flow every $\epsilon\mu$
insertions, we have that $F^{*}\leq F^{*}_{0}+\epsilon\mu$. Since
$F^{*}_{0}>\mu$ and $F=F^{*}_{0}\geq 1$, bringing these together yields:

$\displaystyle\frac{F^{*}}{F}$
$\displaystyle\leq\frac{F^{*}_{0}+\epsilon\mu}{F}\leq\frac{(1+\epsilon)F^{*}_{0}}{F^{*}_{0}}\leq
1+\epsilon,$

which proves our claimed approximation guarantee.

We next study the running time. Note that our algorithm passes the edge
insertions to the incremental algorithm IncBMF (invoked with the parameter
$\mu+1$) only if the value of the maximum flow in the current graph is bounded
by $\mu$. Hence, by the theorem assumption, the total update time to handle
these insertions is $t_{\textrm{total}}(m,n,\mu+1)+mq(m,n)$. Amortizing the
latter over $m$ insertions gives an amortize cost of
$t_{\textrm{total}}(m,n,\mu+1)/m+q(m,n)$, which in turn gives the first and
the third term of our claimed running time guarantee.

It remains to analyse the cost of periodical rebuilds. Note that if the
current maximum flow value is larger than $\mu$, our algorithm updates the
estimate $F$ every $\epsilon\mu$ operations. By assumption of the theorem, the
time to compute an exact maximum flow is
$t_{\textrm{static}}(m^{\prime},n)\leq t_{\textrm{static}}(m,n)$ as
$m^{\prime}\leq m$. Charging this time over $\epsilon\mu$ insertions, yields
an amortized cost of $t_{\textrm{static}}(m,n)/(\epsilon\mu)$, which in turn
gives the second term our of claimed runtime guarantee and completes the proof
of the theorem. ∎

##  4 Incremental Bounded Maximum Flow

In this section we give an incremental algorithm for exactly maintaining the
maximum flow as long as its value is bounded by a predefined parameter $\mu$.
The algorithm applies to directed, unweighted graphs, was initially observed
by Henzinger [13] and later by Gupta and Khan [10], and can be thought of as
an incremental version of the celebrated Ford-Fulkserson algorithm [7]. We
review it below and slightly adapt it for our purposes.

Henzinger [13] showed how to incrementally maintain maximum $s$-$t$ flow in
$O(F^{*})$ amortized update time, where $F^{*}$ is the value of the maximum
flow in the final graph. As there are graphs where $F^{*}=\Omega(n)$, their
running time guarantee is competitive only when $F^{*}$ is small, e.g., sub-
linear on the size of the graph. We next show to slightly adapt their
algorithm so that it maintains a maximum flow as long as its value is bounded
by a parameter $\mu$.

The key observation behind this algorithm is that the insertions of an (unit-
capacitated) edge can only increase the maximum flow value by at most $1$. To
check whether this value has increased, they use Lemma 2.1 as a certificate,
i.e., one determines whether the insertion of the (forward) edge in the
residual graph $G_{f}$ creates a directed path from $s$ to $t$ in $G_{f}$. A
naive way to determine this is to run a graph search algorithm on $G_{f}$
after each insertions, which requires $\Omega(m)$ for a single update and is
thus prohibitively expensive for our purposes. However, one can exploit a data
structure due to Italiano [14] for incrementally maintaining single source
reachability information from a source $s$ which requires $O(m)$ total update
time for handling $m$ insertions. Let us briefly review this data structure
before presenting the incremental algorithm.

### Incremental Single Source Reachability.

In the incremental single source reachability problem, given an (initially
empty) directed, unweighted graph $G=(V,E)$ and a distinguished vertex $s$,
the goal is to construct a data structure IncSSR that supports the following
operations: (i) Initialize$(G,s)$: initialize the data structure in $G$ with
source $s$, (ii) $\textsc{Insert}(u,v)$: insert the edge $(u,v)$ in $G$, and
(iii) Reach$(u)$: return True if $u$ is reachable from $s$, and False
otherwise.

Italiano [14] observed that an incremental version of graph search leads to an
efficient incremental IncSSR data structure. The main idea is to maintain a
reachability tree $T$ from $s$. Initially, the tree is initialized to
$\\{s\\}$. Upon insertion of an edge $(u,v)$ to $G$, we need to update $T$ iff
$u\in T$ and $v\not\in T$. If this is the case, we add $(u,v)$ to $T$ and make
the $v$ the child of $u$. Moreover, the algorithm examines all outgoing
neighbors $w$ incident to $v$, and if $w\not\in T$, processes the edge $(v,w)$
recursively using the same procedure. To answer queries, we return True if
$u\in T$, and False otherwise. These procedures are summarized in Algorithm 2.

1

2Procedure  _Initialize(_$G=(V,E)$ , $s$_)_

3 Set $T\leftarrow\\{s\\}$ and $E\leftarrow\emptyset$

4

5Procedure  _Insert(_$u,v$_)_

6 $E\leftarrow E\cup\\{(u,v)\\}$

7 UpdateTree(_$u,v$_)

8

9Procedure  _UpdateTree(_$u,v$_)_

10 if  _$u\in T$ and $v\not\in T$_ then

11 Make $v$ a child of $u$ in $T$

12 foreach  _$(v,w)\in E$_ do

13 UpdateTree(_$v,w$_)

14

15

16

17Procedure  _Reach(_$u$_)_

18 if  _$u\in T$_ then

19 return True

20 else

21 return False

22

23

Algorithm 2 Incremental Single Source Reachability (IncSSR)

The correctness of the data structure immediately follows by construction as
we always maintain a correct rechability tree $T$ from $s$ for the current
graph. For the running time, note that the total time over all insertions is
$O(m)$ as each edge is processed at most $O(1)$ times, once when it is
inserted into the graph and once when it is added to $T$.

######  Lemma 4.1 ([14]).

Given an initially empty directed, unweighted graph $G=(V,E)$ and a source
vertex $s$, the incremental algorithm IncSSR maintains reachability
information from $s$ to every other node in $V$ while supporting insertions in
$O(1)$ amortized update time and queries in $O(1)$ in worst-case time.

### The Algorithm.

We now have all the necessary tools to present an incremental algorithm
maintaining the maximum flow whose value is bounded by $\mu$. Let $F^{*}$
denote the maximum $s$-$t$ flow value on the current graph.

Initially, $G$ and the residual graph $G_{f}$ are empty graphs,
$F^{*}\leftarrow 0$ and $f(e)\leftarrow 0$ for each $e\in E$. The algorithm
proceeds in $\mu$ rounds, where a round ends when the value of the current
maximum flow increases by one. Each round starts by initializing an
incremental single source reachability data structure IncrSSR from the source
$s$ (Lemma 4.1) on the residual graph $G_{f}$. Upon an edge insertion $(u,v)$
to $G$, we pass the directed edge $(u,v)$ to the data structure IncrSSR and
test whether $t$ is reachable from $s$ using this data-structure. If the
latter holds, then we find a simple directed $s$-$t$ path $P$ in $G_{f}$,
which in turn serves as an augmenting path for $G$. We then send one unit of
flow along the path $P$ in $G$ and update the current flow and its value
accordingly. To answer a query about the maximum flow between $s$ and $t$, we
simply return $F^{*}$. These procedures are summarized in Algorithm 3.

1

2Procedure  _Initialize(_$G=(V,E)$ , $s$, $t$, $\mu$_)_

3 Set $E\leftarrow\emptyset$

4 Set $f(e)\leftarrow 0$ for each $e\in E$, $G_{f}\leftarrow(V,E)$ and
$F^{*}\leftarrow 0$

5 Invoke $\textsc{IncSSR}.\textsc{Initialize}(G_{f},s)$

6

7Procedure  _Insert(_$u,v$_)_

8 if  _$F^{*}\leq\mu$_ then

9 $E\leftarrow E\cup\\{(u,v)\\}$

10 Invoke $\textsc{IncSSR}.\textsc{Insert}(u,v)$

11 if  _$\textup{{IncSSR}.{Reach}}(t)$_ then

12 Find a simple directed $s$-$t$ path $P$ in $G_{f}$

13 Augment $f$ along the path $P$ in $G$ and let $f^{\prime}$ be the resulting
flow

14 Set $f\leftarrow f^{\prime}$ and $G_{f}\leftarrow G_{f^{\prime}}$

15 Set $F^{*}\leftarrow F^{*}+1$

16 Invoke $\textsc{IncSSR}.\textsc{Initialize}(G_{f},s)$

17

18

19

20Procedure  _MaxFlow(_$s,t$_)_

21 return $F^{*}$

Algorithm 3 Incremental Bounded Maximum Flow (IncBMF)

The correctness of this algorithm is immediate by Lemma 2.1, which correctly
tells us when to increase the value of the maximum flow, and Fact 2.2, which
asserts that the sending one unit of flow along an augmenting path increase
the value of the flow by exactly one.

For the running time, note that each round requires $O(m)$ total time. As
there are exactly $\mu$ stages, we get a total update time of $O(m\mu)$.

######  Theorem 4.2.

Given an initially empty directed, unweighted graph $G=(V,E)$ with $n$
vertices, any two vertices $s$ and $t$, and a parameter $\mu\in[0,n]$, the
algorithm IncBMF$(G,s,t,\mu)$ exactly maintains, under $m$ edge insertions,
the maximum $s$-$t$ flow in $G$ whose value is bounded by $\mu$ in $O(m\mu)$
total update time and $O(1)$ query time.

## Acknowledgement

We thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster and Sushant
Sachdeva for helpful discussions.

_M. Henzinger:_ This project has received funding from the European Research
Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic
Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF)
project “Fast Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N,
with additional funding from the netidee SCIENCE Stiftung, 2020–2024.

## References

  * [1] Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng.  On fully dynamic graph sparsifiers.  In Symposium on Foundations of Computer Science (FOCS), pages 335–344, 2016.
  * [2] Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak.  Fast dynamic cuts, distances and effective resistances via vertex sparsifiers.  In Symposium on Foundations of Computer Science (FOCS), 2020.
  * [3] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  CoRR, abs/2203.00671, 2022.
  * [4] Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau.  Fast matrix rank algorithms and applications.  J. ACM, 60(5):31:1–31:25, 2013.
  * [5] Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng.  Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs.  In Symposium on Theory of Computing (STOC), pages 273–282, 2011\.
  * [6] Søren Dahlgaard.  On the hardness of partially dynamic graph problems and connections to diameter.  In International Colloquium on Automata, Languages, and Programming (ICALP), pages 48:1–48:14, 2016.
  * [7] LR Ford and DR Fulkerson.  Flows in networks.  1962\.
  * [8] R. E. Gomory and T. C. Hu.  Multi-terminal network flows.  Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961.
  * [9] Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan.  The expander hierarchy and its applications to dynamic graph algorithms.  In Symposium on Discrete Algorithms (SODA), 2021.
  * [10] Manoj Gupta and Shahbaz Khan.  Simple dynamic algorithms for maximal independent set and other problems.  CoRR, abs/1804.01823, 2018.
  * [11] Manoj Gupta and Richard Peng.  Fully dynamic (1+ e)-approximate matchings.  In Symposium on Foundations of Computer Science (FOCS), pages 548–557, 2013.
  * [12] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Symposium on Theory of Computing (STOC), pages 21–30, 2015.
  * [13] Monika Rauch Henzinger.  A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity.  J. Algorithms, 24(1):194–220, 1997.
  * [14] Giuseppe F. Italiano.  Amortized efficiency of a path retrieval data structure.  Theor. Comput. Sci., 48(3):273–281, 1986.
  * [15] Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen.  Improved algorithms for min cut and max flow in undirected planar graphs.  In Symposium on Theory of Computing (STOC), pages 313–322, 2011\.
  * [16] Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford.  An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations.  In Symposium on Discrete Algorithms (SODA), pages 217–226, 2014\.
  * [17] Rohit Khandekar, Satish Rao, and Umesh V. Vazirani.  Graph partitioning using single commodity flows.  J. ACM, 56(4):19:1–19:15, 2009.
  * [18] Yang P. Liu and Aaron Sidford.  Faster divergence maximization for faster maximum flow.  In Symposium on Foundations of Computer Science (FOCS), 2020.
  * [19] Aleksander Madry.  Navigating central path with electrical flows: From flows to matchings, and back.  In Symposium on Foundations of Computer Science (FOCS), pages 253–262, 2013.
  * [20] Aleksander Madry.  Computing maximum flow with augmenting electrical flows.  In Symposium on Foundations of Computer Science (FOCS), pages 593–602, 2016.
  * [21] Richard Peng.  Approximate undirected maximum flows in _O_(_m_ polylog(_n_)) time.  In Symposium on Discrete Algorithms (SODA), pages 1862–1867, 2016\.
  * [22] Jonah Sherman.  Nearly maximum flows in nearly linear time.  In Symposium on Foundations of Computer Science (FOCS), pages 263–269, 2013.
  * [23] Jonah Sherman.  Area-convexity, l${}_{\mbox{{$\infty$}}}$ regularization, and undirected multicommodity flow.  In Symposium on Theory of Computing (STOC), pages 452–460, 2017\.