# Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update
Time

Sayan Bhattacharya Supported by Engineering and Physical Sciences Research
Council, UK (EPSRC) Grant EP/S03353X/1. University of Warwick  Peter Kiss Work
done in part while the author was visiting Max-Planck-Institut für Informatik
University of Warwick  Thatchaphol Saranurak  University of Michigan, Ann
Arbor  David Wajc Work done in part while the author was at Stanford
University. Google Research

###### Abstract

We present dynamic algorithms with _polylogarithmic_ update time for
estimating the size of the maximum matching of a graph undergoing edge
insertions and deletions with approximation ratio _strictly better than $2$_.
Specifically, we obtain a $1+\frac{1}{\sqrt{2}}+\epsilon\approx
1.707+\epsilon$ approximation in bipartite graphs and a $1.973+\epsilon$
approximation in general graphs. We thus answer in the affirmative the value
version of the major open question repeatedly asked in the dynamic graph
algorithms literature. Our randomized algorithms’ approximation and worst-case
update time bounds both hold w.h.p. against adaptive adversaries.

Our algorithms are based on simulating new two-pass streaming matching
algorithms in the dynamic setting. Our key new idea is to invoke the recent
sublinear-time matching algorithm of Behnezhad (FOCS’21) in a white-box manner
to efficiently simulate the second pass of our streaming algorithms, while
bypassing the well-known vertex-update barrier.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Results
    2. 1.2 Our Techniques
    3. 1.3 Further Related Work
      1. 1.3.1 Concurrent work
  2. 2 Preliminaries
    1. 2.1 Previous building blocks
    2. 2.2 New algorithmic primitive: Robust Approximately Maximal Matchings
  3. 3 Algorithms on Bipartite Graphs
    1. 3.1 Two-Pass Streaming Algorithm
    2. 3.2 Dynamic Algorithm
  4. 4 Algorithms on General Graphs
    1. 4.1 Two-Pass Streaming Algorithm
    2. 4.2 Dynamic Algorithms
      1. 4.2.1 Breaking the barrier of two in polylog time
      2. 4.2.2 New time/approximation tradeoffs
  5. 5 AMMs against Adaptive Adversaries
    1. 5.1 From kernels to AMMs
    2. 5.2 Periodic kernels and AMMs
    3. 5.3 Robust dynamic AMMs
  6. 6 Conclusion and Future Directions
  7. A Proofs of basic building blocks
    1. A.1 Proof of Proposition 2.1
    2. A.2 Proof of Proposition 2.6
  8. B Proof of Lemma 4.6
    1. B.1 Building blocks
    2. B.2 The algorithm
  9. C Omitted Proofs from Section 4.1
  10. D Omitted Proofs of Section 5

##  1 Introduction

The maximum matching problem is a cornerstone of combinatorial optimization
and theoretical computer science more broadly. (We recommend [DP14] for a
brief history of this problem.) The study of this problem and its extensions
has contributed foundational advances and concepts to the theory of computing,
from the introduction of the primal-dual method [Kuh55], impact on polyhedral
combinatorics [Edm65a], and the advocacy for polynomial-time computability as
the measure of efficiency (in static settings) [Edm65b].

The maximum matching problem has also been intensely studied in _dynamic_
settings. Here, the graph undergoes edge _updates_ (insertions and deletions),
and we wish to approximate the maximum matching, while spending little
computation time between updates, referred to as _update time_. Polynomial
update time is trivial to achieve by running exact static algorithms (e.g.,
[Edm65b]) after each update. However, intuitively, such minor changes to the
graph should allow for much faster algorithms, with possibly even
exponentially smaller, _polylogarithmic_ update times.

The first sublinear (i.e., $o(m)=o(n^{2})$) update time dynamic matching
algorithm was given 15 years ago by Sankowski [San07], who used fast dynamic
matrix inversion to maintain the maximum matching size in update time
$O(n^{1.495})$, recently improved to $O(n^{1.407})$ [BNS19]. Unfortunately, a
number of fine-grained complexity results rule out fast, and even sublinear-
in-$n$ update time [AVW14, HKNS15, AD16, Dah16, KPP16] for (exact) maximum
matching size estimation. This motivates the wealth of work on computing
_approximate_ matchings dynamically.

The first polylogarithmic update time dynamic matching algorithm is due to an
influential work of Onak and Rubinfeld [OR10], who gave a (large) constant
approximation in polylog update time. This was later improved by Baswana et
al. [BGS15] to a $2$-approximation in logarithmic update time, later improved
to constant time by Solomon [Sol16]. Numerous other algorithms achieving a
$2$\- or $(2+\epsilon)$-approximation in polylog update time were subsequently
developed, with expected amortized update time improved to worst-case
w.h.p.,111An algorithm has _amortized_ update time $f(n)$ if every sequence of
$t$ updates starting from an empty graph takes at most $t\cdot f(n)$ update
time. If each operation takes at most $f(n)$ time, it has _worst-case_ update
time $f(n)$. and oblivious randomized algorithms improved to advsersarially-
robust ones, and then to deterministic ones [BHN16, ACC+18, CS18, BFH19, BK19,
BDH+19, CZ19, Waj20, BK21, Kis22].222An algorithm _works against an adaptive
adversary_ if its guarantees hold even when future updates depend on the
algorithm’s previous output. We also say that such an algorithm is
_adversarially robust_ , or _robust_ for short. The importance of robustness
for _static_ applications has motivated a recent concentrated effort to design
robust dynamic algorithms for myriad problems (see, e.g., discussions in
[NS17, BKM+22, Waj20, BK21, CK19, FMP+18]).

A complementary line of work studied better-than-two-approximate dynamic
matching, providing a number of small polynomial (even sublinear in $n$)
update times for approximation ratios below the natural bound of $2$ achieved
by inclusionwise maximal matchings. This includes $(1+\epsilon)$-approximate
algorithms with $O_{\epsilon}(\sqrt{m})=O_{\epsilon}(n)$ update time [GP13,
PS16], $\left(\frac{3}{2}+\epsilon\right)$-approximate algorithms with
$O_{\epsilon}(\sqrt[4]{m})=O_{\epsilon}(\sqrt{n})$ update time [BS15, BS16,
GSSU22, Kis22] and a number of tradeoffs between approximation in the range
$(3/2,2)$ and sublinear-in-$n$ polynomial update times [BLM20, Waj20, BK21,
BK22, RSW22].333Throughout the paper, we use $O_{\epsilon}(\cdot)$ to suppress
$\mathrm{poly}(1/\epsilon)$ factors and $\tilde{O}(\cdot)$ to suppress
$\mathrm{poly}(\log n)$ factors.

This state of affairs leaves open a key question, repeatedly raised in the
literature [BHN16, BS16, CS18, BLM20, Waj20, BK22, LMSVW22] and first posed by
Onak and Rubinfeld in their aforementioned groundbreaking work [OR10]:

> _How small can [approximation factors] be made with polylogarithmic update
> time? […] Can the approximation constant be made smaller than 2 for maximum
> matching?_
>

###  1.1 Our Results

We resolve the question of polylogarithmic update time better-than-two-
approximate dynamic matching algorithms in the affirmative, _for the value
version of the problem_. That is, letting $\mu(G)$ denote the maximum matching
size in $G$, we maintain an estimate $\nu$ that is $\alpha<2$ approximate,
i.e., it satisfies $\nu\leq\mu(G)\leq\alpha\cdot\nu$ at every point in time.
Our main result is the following.

######  Theorem 1.1.

For every $\epsilon\in(0,1)$, there exists a randomized
$(1.973+\epsilon)$-approximate dynamic matching size estimation algorithm with
$\mathrm{poly}(\log n,1/\epsilon)$ worst-case update time. Both the
algorithm’s approximation ratio and update time hold w.h.p against an adaptive
adversary.

For bipartite graphs, we obtain a stronger approximation guarantee of
$1+\frac{1}{\sqrt{2}}+\epsilon\approx 1.707+\epsilon$.

##### Secondary results.

Our approach is versatile, and yields the following generic reduction.

######  Theorem 1.2.

For any $\alpha>1.5$, a dynamic $\alpha$-approximate matching algorithm with
update time $t_{u}$ implies a dynamic
$\left(\alpha-\Omega\left(\left(1-6\left(\frac{1}{\alpha}-\frac{1}{2}\right)\right)^{2}\right)\right)$-approximate
matching _size estimator_ with update time $\tilde{O}(t_{u})$.

Very recently, Behnezhad and Khanna [BK22] presented new dynamic matching
algorithms trading off approximations $\alpha\in(1.5,2]$ and small polynomial
update times. Applying 1.2 to their algorithms, we obtain improved
approximation for dynamic matching size estimation, within the same update
time up to polylog factors.

To obtain our main results, we design several $2$-pass _semi-streaming_
algorithms (see Section 1.3), including a deterministic
$(1+1/\sqrt{2}+\epsilon)$-approximate algorithm on bipartite graphs. This
matches the prior state-of-the-art [KN21, Kon18] up to an $\epsilon$ term,
while removing the need for randomization.

###  1.2 Our Techniques

We take the following high-level approach to prove 1.1: (1) compute a maximal
(and hence $2$-approximate) matching $M_{1}$, and (2) augment $M_{1}$ if it is
no better than $2$-approximate, using the myriad short augmenting paths
$M_{1}$ must have in this case. This approach is common in many computational
models, including the 2-pass semi-streaming model (see Section 1.3).
Implementing this approach in a dynamic setting, however, faces several
challenges. The first challenge if we want robust algorithms with low worst-
case update times is that no robust (near-)maximal matching algorithms with
worst-case $\tilde{O}_{\epsilon}(1)$ update time are known. Of possible
independent interest, we resolve this first challenge in Section 5, by
leveraging the robust fast matching sparsifiers of [Waj20].

The more central challenge when trying to implement the above approach is that
the search for augmenting paths requires us to find many (disjoint) edges
between matched and unmatched nodes in $M_{1}$. In a (multi-pass) streaming
setting, this can be done by computing a large ($b$-)matching in the bipartite
graph induced by edges in $V(M_{1})\times\overline{V(M_{1})}$. In a dynamic
setting, however, this requires us to deal with _vertex updates_ , which are
notoriously challenging in the context of dynamic matching, and all algorithms
to date require reading all $\Omega(n)$ edges of each updated vertex
[LMSVW22].

To overcome the above key challenge, we first note that we do not need to
handle vertex updates individually, but may instead process these in _batches_
of $\Theta(\epsilon n)$ vertex updates, building on the periodic recomputation
and sparsification techniques common in the literature (see 2.1). Our main
observation is that these batches of vertex updates, which need to be handled
if we wish to maintain the $b$-matchings from the second pass of our semi-
streaming algorithms, can be implemented in $\tilde{O}_{\epsilon}(n)$ time
using the sublinear-time algorithm of Behnezhad [Beh22]. This leads to an
amortized ${\tilde{O}_{\epsilon}(n)}/({\epsilon n})=\tilde{O}_{\epsilon}(1)$
additive overhead in the update time (easily deamortized), implying our main
result. This approach is versatile, and similarly underlies our secondary
results.

###  1.3 Further Related Work

Having discussed the rich literature on the dynamic matching problem above, we
do not elaborate on it further here. We do, however, highlight some
connections to the literature on matching in other computational models that
is closely related to our work.

##### Streaming Matching.

In the (semi-)streaming model, an $n$-node graph is revealed in a stream, edge
by edge, and we wish to compute a large matching using only (optimal)
$\tilde{O}(n)$ space. A line of work studying the problem of computing an
approximately-maximum weighted matching [FKM+05, McG05, ELSW13, CS14, PS18,
GW19] culminated in a $\left(2+\epsilon\right)$-approximation [PS18, GW19].
For unweighted graphs, lower bounds are known [GKK12, Kap13, Kap21], but it
remains a major open question whether one can break the barrier of
$2$-approximation achievable by a trivial maximal matching algorithm. Striving
for better approximation (and insights to break this barrier), several works
designed algorithms using _multiple passes_ over the stream [McG05, KT17,
FS22, EHM16, AG13, EKS09, FMU22, EKS09, AG13, AJJ+22]. For $2$ passes, the
state-of-the-art approximation ratios are $1.857$ [FS22], and
$1+\frac{1}{\sqrt{2}}\approx 1.707$ for bipartite graphs using the randomized
algorithms of [Kon18, KN21], with the best prior deterministic bound being
$\frac{12}{7}\approx 1.714$ [EHM16].

##### Sublinear-Time Matching.

Computation of large matchings in sublinear _time_ has also been the subject
of great interest. In regular bipartite graphs, a maximum matching can be
computed in $\tilde{O}(n)$ time [GKK09, GKK10, GKK13]. In general graphs with
bounded-degrees, it was known how to achieve a $(2+\epsilon)$-approximation in
sublinear time [NO08, ORRR12, PR07, YYI12]. This was recently improved to a
$\tilde{O}(n)$ time algorithm for any general graph [Beh22]. As discussed in
Section 1.2, we use this latter algorithm in a white-box manner to obtain our
main result.

####  1.3.1 Concurrent work

Independently and concurrently, Behnezhad [Beh23] (in a work in the same
conference) obtained the same main qualitative result as ours: a better-than-
two-approximate polylogarithmic time dynamic matching size estimation
algorithm. The basic approach to achieve this qualitative result is the same
in both papers: Simulate the second pass of a two-pass streaming algorithm
using the sublinear-time algorithm of [Beh22], together with batched
computation. The quantitative differences in the papers’ approximation ratios
are due to the two-pass streaming algorithms used—our new maximal-b-matching-
based algorithms here, and an algorithm inspired by [KMM12] in [Beh23]. We
note that [Beh23] also achieves $(3/2-\Omega(1))$-approximate size estimation
algorithm in time ${O}(\sqrt{n})$ (the best update times for
$(3/2+\epsilon)$-approximate explicit matching [BS15, BS16, GSSU22, Kis22]).
This result also uses the high-level approach of batched computation using
sublinear-time algorithms, building on a new characterization of tight
examples for the $3/2$-approximate matching sparsifiers (EDCS) of [BS15].

##  2 Preliminaries

Our input is a graph $G$ on $n$ nodes $V$, with an initially empty edge set
$E$, undergoing edge updates (insertions and deletions). Our objective is to
approximate the maximum matching size $\mu(G)$ well, while spending little
update time (computation between updates). In addition, we want our algorithms
to work in the strictest settings: against an adaptive adversary (i.e., their
guarantees hold for any update sequence), and with small _worst-case_ update
time guarantees.

##### Matching theory basics.

A _matching_ is a vertex-disjoint subset of edges. A _maximal matching_ is an
inclusionwise-maximal matching. A maximum matching is a matching of largest
cardinality. In a weighted graph with edge weights $w_{e}\in\mathbb{R}$, a
maximum weight matching is a matching $M$ of largest total weight,
$w(M):=\sum_{e\in M}w_{e}$. An _augmenting path_ $P$ with respect to a
matching $M$ is a simple path starting and ending with distinct nodes
unmatched in $M$, with the edges alternatingly outside and inside $M$. Setting
$M\leftarrow M\bigoplus P$, where $\bigoplus$ denotes the symmetric
difference, referred to as _augmenting_ $M$ along $P$, increases the
cardinality of $M$ by one. A _$b$ -matching_ with capacities
$\\{b_{v}\\}_{v\in V}$ is a collection of _multi-edges_ $F$ of $E$ (that is,
edges of $E$ may appear multiple times in $F$) with no vertex $v$ having more
than $b_{v}$ multi-edges in $F$. A _fractional matching_
$x:E\to\mathbb{R}_{\geq 0}$ assigns non-negative values to edges so that each
vertex $v$ has _fractional degree_ $\sum_{e\ni v}x_{e}$ at most one. In
bipartite graphs, the existence of a fractional matching of size $k$ implies
the existence of an integral matching of cardinality $\lceil k\rceil$. In
general graphs, this fractional relaxation has a maximum integrality gap of
$3/2$, attained by a triangle graph with values $x_{e}=1/2$ for each edge $e$.

##### Notation:

Let $V(M)$ denote the set of all endpoints of edges in a matching $M$, and let
$\overline{V(M)}:=V\setminus V(M)$. For any disjoint vertex sets $A,B\subseteq
V$, we let $G[A,B]$ denote the bipartite subgraph induced by the edges in $G$
with one endpoint in $A$ and another in $B$. Finally, for any subset of edges
$E^{\prime}\subseteq E$, we let $G[E^{\prime}]$ denote the subgraph of $G$
induced by $E^{\prime}$.

###  2.1 Previous building blocks

A ubiquitous paradigm in the approximate dynamic matching literature is
_periodic recomputation_ , introduced by Gupta and Peng [GP13]. This approach
is particularly useful in conjunction with sparsification techniques. We will
use the vertex sparsification technique introduced by Assadi et al. [AKL19] in
the context of stochastic optimization, and adapted to dynamic settings by
Kiss [Kis22]. Combined, these approaches yield the following “reduction” from
dynamic matching algorithms with _immediate_ queries to ones with slower query
time.

######  Proposition 2.1.

Let $\epsilon\in(0,1)$ and $\alpha\geq 1$. Suppose there exists an algorithm
$\mathcal{A}$ on a dynamic $n$-node graph $G$ with update time $t_{u}$, that,
provided $\mu(G)\geq\epsilon\cdot n$, supports $t_{q}$-time
$\alpha$-approximate size estimate queries w.h.p. Then, there is another
algorithm $\mathcal{A}^{\prime}$ on $G$ that always maintains an
$(\alpha+O(\epsilon))$-approximate estimate $\nu^{\prime}$ in
$\tilde{O}_{\epsilon}(t_{u}+t_{q}/n)$ update time. Moreover if the update time
of $\mathcal{A}$ is worst-case, so is that of $\mathcal{A}^{\prime}$, and if
$\mathcal{A}$ works against an adaptive adversary, then so does
$\mathcal{A}^{\prime}$.

The above proposition, implicit in prior work, serves as a useful abstraction,
and so we provide a proof of this proposition for completeness in Appendix A.
As discussed in Section 1.2, this reduction is one of the crucial ingredients
that allows us to bypass the vertex-update barrier.

Another key ingredient we use is the sublinear-time (approximate) maximal
matching algorithm of Benhezhad [Beh22], whose guarantees are captured by the
following proposition (see Appendix A).

######  Proposition 2.2.

Let $\epsilon\in(0,1/2)$. Using $\tilde{O}_{\epsilon}(n)$ time and
$\tilde{O}_{\epsilon}(n)$ adjacency matrix queries w.h.p. in an $n$-node graph
$G$, one can compute a value $\nu$ which approximates $\tilde{\mu}$, the size
of some maximal matching in $G$, within additive error $\epsilon n$. Namely,
$\tilde{\mu}\geq\nu\geq\tilde{\mu}-\epsilon n.$

A simple combination of propositions 2.1 and 2.2 (with
$t_{q}=\tilde{O}_{\epsilon}(n)$) immediately yields (yet) another
$\tilde{O}_{\epsilon}(1)$-time $(2+\epsilon)$-approximation algorithm. As we
will show, these propositions are also useful ingredients for breaking the
barrier of $2$-approximation within the same update time.

###  2.2 New algorithmic primitive: Robust Approximately Maximal Matchings

To make our algorithms robust against adaptive adversaries we need an
algorithm for maintaining _approximately-maximal matchings_ (AMM), which are
defined as follows.

######  Definition 2.3 ([PS16]).

A matching $M$ is an _$\epsilon$ -approximately maximal matching
($\epsilon$-AMM)_ in graph $G$ if $M$ is maximal in some subgraph obtained by
removing at most $\epsilon\cdot\mu(G)$ nodes of $G$.

######  Observation 2.4.

If $M$ is an $\epsilon$-AMM in $G$, then
$|M|\geq\frac{1}{2}(1-\epsilon)\cdot\mu(G)=\left(\frac{1}{2}-\frac{\epsilon}{2}\right)\cdot\mu(G)$.

Peleg and Solomon [PS16] showed how to maintain an $\epsilon$-AMM quickly in
bounded-arboricity (i.e., globally sparse) graphs. In Section 5 we show how to
maintain such matchings quickly in arbitrary graphs, proving the following.

######  Lemma 2.5.

For any $\epsilon\in(0,1)$, there exists a robust dynamic algorithm that
w.h.p. maintains an $\epsilon$-AMM in worst-case update time
$\tilde{O}_{\epsilon}(1)$.

A well-known fact is that a maximal matching that is close to $2$-approximate
must admit many length-three augmenting paths (see e.g., [KMM12, Lemma 1]).
Our interest in AMMs is in part motivated by the following slight
generalization of this fact.

######  Proposition 2.6.

Let $\epsilon>0$ and $c\in\mathbb{R}$ and let $M$ be an $\epsilon$-AMM in $G$
such that $|M|\leq\left(\frac{1}{2}+c\right)\cdot\mu(G)$. Then $M$ admits a
collection of at least
$\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)\cdot\mu(G)$ node-disjoint
3-augmenting paths.

##  3 Algorithms on Bipartite Graphs

In this section we illustrate our techniques for the special case of bipartite
graphs, for which we obtain an improved approximation ratio of
$1+\frac{1}{\sqrt{2}}+\epsilon\approx 1.707+\epsilon$.

###  3.1 Two-Pass Streaming Algorithm

Here we present our deterministic 2-pass streaming algorithm. We first compute
an approximately-maximal matching $M_{1}$ from the first pass.444We suggest to
the reader to think of $M_{1}$ as a maximal matching (i.e., $\epsilon=0$). We
relax $M_{1}$ to be an $(\epsilon/8)$-AMM since this will be useful in our
dynamic implementation that works against adaptive adversaries. Then, in the
second pass, we compute a maximal $b$-matching $M_{2}$ in the graph between
matched and unmatched vertices, with capacities $k$ and $\lfloor k\cdot
b\rfloor$, respectively, where we set the parameters $k\in\mathbb{Z}$ and
$b\in\mathbb{R}$ later. Finally, we output an estimate
$(1-\delta)\cdot|M_{1}|+(\delta/k)\cdot|M_{2}|$ where $\delta=1/b$. Our
pseudocode is given in Algorithm 1.

Algorithm 1 Bipartite Two-Pass Streaming Algorithm

1: $M_{1}\leftarrow$ $(\epsilon/8)$-AMM in $G$ computed from first pass

2: assign each vertex $v$ capacity $b_{v}=\begin{cases}k&v\in V(M_{1})\\\
\lfloor k\cdot b\rfloor&v\not\in V(M_{1})\end{cases}$

3: $M_{2}\leftarrow$ maximal $b$-matching in $G[V(M_{1}),\overline{V(M_{1})}]$
computed from second pass

4: Output $(1-\delta)\cdot|M_{1}|+(\delta/k)\cdot|M_{2}|$.

First, we prove that the above algorithm’s output estimate corresponds to a
matching in $G$.

######  Observation 3.1.

We have that $\mu(G[M_{1}\cup
M_{2}])\geq(1-\delta)\cdot|M_{1}|+(\delta/k)\cdot|M_{2}|.$

###### Proof.

Since $G$ is bipartite, by the integrality of the bipartite fractional
matching polytope, to prove that $G^{\prime}:=G[M_{1}\cup M_{2}]$ contains a
large matching witnessing the desired inequality, it suffices to prove that
$G^{\prime}$ contains a _fractional_ matching $\vec{x}$ of value
$\sum_{e}x_{e}=(1-\delta)\cdot|M_{1}|+(\delta/k)\cdot|M_{2}|$. Indeed, such a
fractional matching is obtained by assigning edge values

$x_{e}=\begin{cases}1-\delta&e\in M_{1}\\\ \delta/k&e\in M_{2}\setminus
M_{1}.\end{cases}$

This is indeed a fractional matching, since each vertex $v$ has bounded
fractional degree, $\sum_{e\ni v}x_{e}\leq 1$: every vertex $v\in V(M_{1})$
has one incident $M_{1}$ edge and at most $k$ many incident $M_{2}$ edges, and
so $\sum_{e\ni v}x_{e}\leq(1-\delta)+(\delta/k)\cdot k=1$, while every vertex
$v\not\in V(M_{1})$ has no incident $M_{1}$ edge and has at most $k\cdot b$
incident $M_{2}$ edges, and so $\sum_{e\ni v}x_{e}\leq k\cdot
b\cdot(\delta/k)\leq 1$. ∎

By 3.1, Algorithm 1 outputs a valid estimate for the matching size,
$\nu\leq\mu(G)$. It remains to prove that $\nu$ provides a good approximation
of $\mu(G)$. For this, we require the following.

######  Lemma 3.2.

Let $M$ be a maximal $b$-matching in a bipartite graph $G=(L\cup R,E)$, with
positive integral capacities $b_{v}=\ell$ for all $v\in L$ and $b_{v}=r$ for
all $v\in R$. Then

$|M|\geq\mu(G)\cdot\frac{\ell\cdot r}{\ell+r}.$

###### Proof.

Fix a maximum matching $M^{*}$ in $G$. Next, we define the subset of matched
nodes in $M^{*}$ that are also saturated in $M$. That is, if $d_{M}(v)$ is
$v$’s degree in $M$, we let

$\displaystyle L^{*}_{sat}$ $\displaystyle:=\\{u\in L\cap V(M^{*})\mid
d_{M}(u)=\ell\\}$ $\displaystyle R^{*}_{sat}$ $\displaystyle:=\\{v\in R\cap
V(M^{*})\mid d_{M}(v)=r\\}.$

Let $\alpha:=|L^{*}_{sat}|/|M^{*}|$ and $\beta:=|R^{*}_{sat}|/|M^{*}|$ denote
the fraction of $M^{*}$ edges with a saturated $L$ and $R$ node, respectively.
Since $M$ is a maximal $b$-matching in $G$, each edge has at least one
saturated endpoint, and so $\alpha+\beta\geq 1$. By double counting the edges
of $M$, relying on $\alpha+\beta\geq 1$, and noting that $\alpha\cdot
r+(1-\alpha)\cdot\ell$ attains its minimum of $2\frac{\ell\cdot r}{\ell+r}$ at
$\alpha=\frac{r}{\ell+r}$, we obtain the claimed inequality.

$\displaystyle|M|$ $\displaystyle=\frac{1}{2}\left(\sum_{v\in
L}d_{M}(v)+\sum_{v\in R}d_{M}(v)\right)$
$\displaystyle\geq\frac{1}{2}\left(\sum_{v\in L^{*}_{sat}}d_{M}(v)+\sum_{v\in
R^{*}_{sat}}d_{M}(v)\right)$
$\displaystyle=\frac{1}{2}\cdot(|M^{*}|\cdot\alpha\cdot\ell+|M^{*}|\cdot\beta\cdot
r)$
$\displaystyle\geq\frac{1}{2}\cdot\mu(G)\cdot(\alpha\cdot\ell+(1-\alpha)\cdot
r)$ $\displaystyle\geq\mu(G)\cdot\frac{\ell\cdot r}{\ell+r}.\qed$

We are now ready to bound the approximation ratio of Algorithm 1.

######  Lemma 3.3.

For any $\epsilon\in(0,1)$, Algorithm 1 with $b=1+\sqrt{2}$ and
$k\geq\frac{8}{\epsilon b}$ run on bipartite graph $G$ computes a
$(1+\frac{1}{\sqrt{2}}+\epsilon)\approx(1.707+\epsilon)$-approximation to
$\mu(G)$.

###### Proof.

Fix a maximum matching $M^{*}$ in $G$. Next, for $i\in\\{0,1,2\\}$, let
$M^{*}_{i}$ denote the edges of $M^{*}$ with $i$ endpoints matched in $M_{1}$.
By definition, and since $|M_{1}|=\frac{1}{2}\cdot|V(M_{1})|$, we have that

$\displaystyle|M_{1}|=|M^{*}_{2}|+(1/2)\cdot|M^{*}_{1}|.$ (1)

Furthermore, since $M_{1}$ is an $\epsilon^{\prime}$-AMM in $G$ for
$\epsilon^{\prime}=\epsilon/8$, we have that
$|M^{*}_{0}|\leq\epsilon^{\prime}\cdot\mu(G)$, since at most
$\epsilon^{\prime}\cdot\mu(G)$ nodes of $G$ must be removed from $G$ to make
$M_{1}$ maximal, and at least one endpoint of each $M^{*}_{0}$ edge must be
removed to achieve the same effect. But then, since
$M^{*}_{0},M^{*}_{1},M^{*}_{2}$ partition $M^{*}$, whose cardinality is
$|M^{*}|=\mu(G)$, this implies that

$\displaystyle|M^{*}_{1}|+|M^{*}_{2}|\geq(1-\epsilon^{\prime})\cdot\mu(G).$
(2)

Now, by 3.2, since $M^{*}_{1}$ is a matching in graph
$G^{\prime}:=G[V(M_{1}),\overline{V(M_{1})}]$ and
$k\geq\frac{1}{\epsilon^{\prime}b}$, we have

$\displaystyle|M_{2}|\geq\mu(G^{\prime})\cdot\frac{k\cdot\lfloor
kb\rfloor}{k+\lfloor kb\rfloor}\geq\frac{\lfloor
kb\rfloor}{b+1}\cdot|M^{*}_{1}|\geq\frac{kb(1-\epsilon^{\prime})}{b+1}\cdot|M^{*}_{1}|.$
(3)

Combining equations (1), (2) and (3), we obtain the following lower bound on
our output estimate.

$\displaystyle(1-\delta)\cdot|M_{1}|+(\delta/k)\cdot|M_{2}|$
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn:M1-vs-M^*_i},\eqref{eqn:M2-vs-M^*_i}}}{{\geq}}(1-\delta)\cdot\left(|M^{*}_{2}|+(1/2)\cdot|M^{*}_{1}|\right)+(\delta/k)\cdot\frac{kb(1-\epsilon^{\prime})}{b+1}\cdot|M^{*}_{1}|$
$\displaystyle=(1-1/b)\cdot|M^{*}_{2}|+\left(\frac{1-1/b}{2}+\frac{1-\epsilon^{\prime}}{b+1}\right)\cdot|M^{*}_{1}|$
$\displaystyle\geq(|M^{*}_{1}|+|M^{*}_{2}|)\cdot\min\left\\{1-1/b,\,\frac{1-1/b}{2}+\frac{1-\epsilon^{\prime}}{b+1}\right\\}$
$\displaystyle\stackrel{{\scriptstyle\eqref{eqn:M^*_i-vs-
OPT}}}{{\geq}}(1-\epsilon^{\prime})\cdot\mu(G)\cdot\min\left\\{1-1/b,\,\frac{1-1/b}{2}+\frac{1-\epsilon^{\prime}}{b+1}\right\\}$
$\displaystyle\geq(1-2\epsilon^{\prime})\cdot\mu(G)\cdot\min\left\\{1-1/b,\,\frac{1-1/b}{2}+\frac{1}{b+1}\right\\}$
$\displaystyle=(1-2\epsilon^{\prime})\cdot(2-\sqrt{2})\cdot\mu(G),$

where the last equality follows by our choice of $b=1+\sqrt{2}$.

Thus, combining with 3.1, and using that $\epsilon^{\prime}=\epsilon/8<1/8$,
we find that the output matching size estimate
$\nu:=(1-\delta)\cdot|M_{1}|+(\delta/k)\cdot|M_{2}|$ is indeed a
$\left(1+\frac{1}{\sqrt{2}}+\epsilon\right)$-approximation.

$\displaystyle\nu$
$\displaystyle\leq\mu(G)\leq\nu\cdot\left(\frac{1}{(2-\sqrt{2})\cdot(1-2\epsilon^{\prime})}\right)\leq\nu\cdot\left(\left(1+\frac{1}{\sqrt{2}}\right)\cdot(1+4\epsilon^{\prime})\right)\leq\nu\cdot\left(1+\frac{1}{\sqrt{2}}+\epsilon\right).\qed$

######  Remark 3.4.

A direct extension of the tight example of [KN21] proves that this analysis is
tight, up to the exact dependence on $\epsilon$.

3.1 implies a 2-pass streaming algorithm for computing a
$(1+\frac{1}{\sqrt{2}}+\epsilon)$-approximate maximum matching: simply store
$G[M_{1}\cup M_{2}]$ and output a maximum matching in this subgraph by the
stream’s end. The space used in the first and second passes are $\tilde{O}(n)$
and $\tilde{O}(nkb)=\tilde{O}(n/\epsilon)$, respectively. More interestingly
for our goals, we show in the next section that 3.3 can be used to obtain a
_dynamic_ approximation of the same quality, in polylogarithmic update time.

###  3.2 Dynamic Algorithm

In this section, we show how to (approximately) implement Algorithm 1 in
polylogarithmic update time in a dynamic setting.

######  Theorem 3.5.

Let $\epsilon\in(0,1)$. There exists a robust dynamic algorithm $\mathcal{A}$
with worst-case update time $t_{u}=\tilde{O}_{\epsilon}(1)$ w.h.p. and query
time $t_{q}=\tilde{O}_{\epsilon}(n)$ that outputs w.h.p. a value
$\nu\in[\mu(G)/(1+\frac{1}{\sqrt{2}}+\epsilon),\mu(G)]$. That is, it answers
$(1+\frac{1}{\sqrt{2}}+\epsilon)$ approximate matching size estimate queries.

###### Proof.

The dynamic algorithm $\mathcal{A}$ is based on Algorithm 1. Let
$\epsilon^{\prime}=\epsilon/12$. Throughout the updates, Algorithm $\cal{A}$
simply maintains an $(\epsilon^{\prime}/8)$-AMM in $G$, denoted by $M_{1}$,
invoking 2.5. This immediately implies the desired update time of
$t_{u}=\tilde{O}_{\epsilon}(1)$.

We now describe how Algorithm $\mathcal{A}$ responds to a query about the
maximum matching size. To answer this query, the algorithm considers a new
auxiliary graph $G^{*}=(V^{*},E^{*})$, which is defined as follows. Set
$b=1+\sqrt{2}$. For each $u\in V(M_{1})$, create
$k:=\lceil\frac{8}{\epsilon^{\prime}b}\rceil$ copies of the node $u$ in
$G^{*}$. Next, for each $v\in\overline{V(M_{1})}$, create $\lfloor k\cdot
b\rfloor$ copies of the node $v$ in $G^{*}$. Finally, for every edge $(u,v)\in
G\big{[}V(M_{1}),\overline{V(M_{1})}\big{]}$, create an edge in $G^{*}$
between every pair $(u^{*},v^{*})$ of copies of the nodes $u,v$. Note that
there is a one-to-one mapping between maximal matchings in the new graph
$G^{*}$ and maximal $b$-matchings in
$G\big{[}V(M_{1}),\overline{V(M_{1})}\big{]}$.

We emphasize that our dynamic algorithm $\mathcal{A}$ does not explicitly
maintain the auxiliary graph $G^{*}$. When we receive a query about the
maximum matching size in $G$, we explicitly construct only the node-set
$V^{*}$ of $G^{*}$, based on the matching $M_{1}$. This takes only
$O_{\epsilon}(n)$ time since $|V^{*}|=O_{\epsilon}(n)$. We can, however,
access the edges of $G^{*}$ by using adjacency matrix queries: there exists an
edge $(u^{*},v^{*})$ in $G^{*}$ iff there exists an edge $(u,v)$ between the
corresponding nodes in $G$.

At this point, we invoke 2.2 with $G=G^{*}$ and precision parameter
$e^{\prime\prime}=(\epsilon^{\prime})^{3}$. This gives us a value $\psi$,
which is an estimate of $|M_{2}|$. We now return
$\nu:=(1-1/b)\cdot|M_{1}|+(1/bk)\cdot\psi$ as our estimate of $\mu(G)$.
Clearly, this entire procedure for answering a query takes
$\tilde{O}_{\epsilon}(n)$ time. It now remains to analyze the approximation
ratio. Towards this end, we again appeal to 2.2. This proposition asserts that
the value $\psi$ satisfies

$\displaystyle|M_{2}|\geq\psi\geq|M_{2}|-\epsilon^{\prime\prime}\cdot|V^{*}|\geq|M_{2}|-(\epsilon^{\prime})^{2}\cdot
16n\geq|M_{2}|-\epsilon^{\prime}\cdot\mu(G),$ (4)

Therefore, our estimate $\nu$ satisfies that
$\nu^{\prime}\geq\nu\geq\nu^{\prime}-\epsilon\cdot\mu(G)$, where

$\displaystyle\nu^{\prime}:=(1-1/b)\cdot|M_{1}|+(1/bk)\cdot|M_{2}|.$ (5)

Now, by 3.3 and our choice of $k=\lceil\frac{8}{\epsilon^{\prime}b}\rceil$ and
$b=1+\sqrt{2}$, we have that
$\nu^{\prime}\leq\mu(G)\leq\nu^{\prime}\cdot\big{(}1+\frac{1}{\sqrt{2}}+\epsilon\big{)}$,
from which we obtain that $\nu\leq\nu^{\prime}\leq\mu(G)$ and moreover

$\displaystyle\mu(G)\leq\nu^{\prime}\cdot\left(1+\frac{1}{\sqrt{2}}+\epsilon^{\prime}\right)\leq(\nu+\epsilon^{\prime}\cdot\mu(G))\cdot\left(1+\frac{1}{\sqrt{2}}+\epsilon^{\prime}\right)\leq\nu\cdot\left(1+\frac{1}{\sqrt{2}}+\epsilon^{\prime}\right)+3\epsilon^{\prime}\cdot\mu(G).$

Rearranging terms, and using that $\epsilon^{\prime}=\epsilon/16\leq 1/12$, we
have that

$\displaystyle\nu\leq\mu(G)\leq\nu\cdot\left(1+\frac{1}{\sqrt{2}}+\epsilon^{\prime}\right)/(1-3\epsilon)\leq\nu\cdot\left(1+\frac{1}{\sqrt{2}}+\epsilon\right)\cdot(1+4\epsilon)\leq\nu\cdot\left(1+\frac{1}{\sqrt{2}}+16\epsilon^{\prime}\right).$

That is, since $\epsilon^{\prime}=\epsilon/16$, the estimate $\nu$ output
after a query is $\big{(}1+\frac{1}{\sqrt{2}}+\epsilon\big{)}$-approximate,
w.h.p. ∎

Combining 3.5 and 2.1, we obtain our result for bipartite graphs.

######  Theorem 3.6.

For any $\epsilon\in(0,1)$, there exists a
$(1+\frac{1}{\sqrt{2}}+\epsilon)\approx(1.707+\epsilon)$-approximate
randomized dynamic bipartite matching size algorithm with
$\tilde{O}_{\epsilon}(1)$-update time. The algorithm’s approximation ratio
holds w.h.p. against an adaptive adversary.

######  Remark 3.7.

By the same approach as the recent dynamic weighted matching framework of
[BDL21] restricted to bipartite graphs, 3.6 implies a
$\big{(}1+\frac{1}{\sqrt{2}}+\epsilon)$ robust approximation for _weighted_
bipartite matching with the same update time, up to an exponential blowup in
the dependence on $\epsilon$.555This extension is not obtained by using the
framework of [BDL21] directly, as the latter requires explicit dynamic
matchings. Nonetheless, their arguments can be extended to the value version
of the problem.

##  4 Algorithms on General Graphs

In this section we present our main result: a robust dynamic algorithm
maintaining a $(2-\Omega(1))$-approximation to the size of the maximum
matching in a general graph in worst-case $\tilde{O}_{\epsilon}(1)$ update
time. As with our algorithm for bipartite graphs, we start with a two-pass
semi-streaming algorithm in Section 4.1, and then show how to approximately
implement it dynamically in Section 4.2.1. Finally, in Section 4.2.2 we show
that our approach allows us to improve the approximation of any algorithm with
approximation ratio in the range $(1.5,2]$.

###  4.1 Two-Pass Streaming Algorithm

The key challenge in extending Algorithm 1 and its analysis to non-bipartite
graphs is its reliance on the integrality of the fractional matching polytope
in bipartite graphs. This allowed us to focus on proving the existence of a
large fractional matching, which guarantees the existence of a large integral
matching of (at least) the same size. For general graphs this argument fails,
and so instead we search for length-three augmenting paths ($3$-augmenting
paths, for short) with respect to our first matching, $M_{1}$, by computing
some large $b$-matching $M_{2}$ in the edge set
$V(M_{1})\times\overline{V(M_{1})}$. The main difficulty with this approach in
general graphs is that both the endpoints of an edge $(u,v)\in M_{1}$ might
get matched (in $M_{2}$) to the same node $w$, and the resulting triangle
$w-u-v-w$ does not help us in any way to create a $3$-augmenting path
involving the edge $(u,v)\in M_{1}$.

We overcome this difficulty using _random bipartitions_ (see Algorithm 2). As
before, in the first pass we compute an $(\epsilon/4)$-AMM $M_{1}$ in the
input graph $G$.666As with the bipartite Algorithm 1, we suggest the reader
think of $M_{1}$ as being maximal for now (i.e., $\epsilon=0$). Next, we
define the following random bipartition $(L,R)$ of the node-set $V$. For each
matched edge $(u,v)\in M_{1}$, we arbitrarily include one of its endpoints in
$L$ and the other in $R$. Next, for each unmatched node
$v\in\overline{V(M_{1})}$, we include the node $v$ in into one of $L$ and $R$
chosen uniformly at random. Subsequently, we assign a capacity $b_{v}:=1$ to
all nodes $v\in V(M_{1})$ and a capacity $b_{v}:=b$ to all nodes
$v\in\overline{V(M_{1})}$, for some integer $b$ to be chosen later. Let
$B=(V,E_{2})$ be the bipartite subgraph spanned by edges with a single node
matched in $M_{1}$ and endpoints in opposite sides, i.e.,

$E_{2}:=\\{(u,v)\in E\mid u\in
V(M_{1}),\,v\in\overline{V(M_{1})},\,|\\{u,v\\}\cap L|=|\\{u,v\\}\cap
R|=1\\}).$

In the second pass, we compute a maximal $b$-matching $M_{2}$ in $B$ w.r.t.
the capacities $\\{b_{v}\\}$. Finally, we return the maximum matching in the
subgraph $G[M_{1}\cup M_{2}]$.

Algorithm 2 General Two-Pass Streaming Algorithm

1: $M_{1}\leftarrow$ $(\epsilon/4)$-AMM computed from first pass

2: for edge $(u,v)\in M_{1}$ do

3: $s(u)\leftarrow\ell$ and $s(v)\leftarrow r$

4: for vertex $w\in\overline{V(M_{1})}$ do

5: $s(w)\sim\textrm{Uni}\\{\ell,r\\}$

6: let $L\leftarrow\\{v\mid s(v)=\ell\\}$ and $R\leftarrow\\{v\mid s(v)=r\\}$

7: Assign each vertex $v$ capacity $b_{v}=\begin{cases}1&v\in V(M_{1})\\\
b&v\in\overline{V(M_{1})}.\end{cases}$

8: let $B\leftarrow(V,E_{2})$, for $E_{2}=\\{(u,v)\in E\mid u\in
V(M_{1}),v\in\overline{V(M_{1})},|\\{u,v\\}\cap L|=|\\{u,v\\}\cap R|=1\\})$.

9: $M_{2}\leftarrow$ maximal $b$-matching in $B$ computed from second pass

10: Output maximum matching in $G[M_{1}\cup M_{2}]$

Intuition: The intuition behind Algorithm 2 is as follows: if $M_{1}$ is only
roughly $2$-approximate, then many $3$-augmenting paths exist in $G$ w.r.t.
$M_{1}$, by 2.6. Now, a constant fraction of these (specifically, a quarter)
“survive” the random bipartition and have their extreme edges belong to $B$.
Now, for each augmenting path $u^{\prime}-u-v-v^{\prime}$ that survives,
either an augmenting path containing $u-v$ is found in $M_{1}\cup M_{2}$, or
at least one of $u^{\prime}$ or $v^{\prime}$ is matched $b$ times to nodes in
$V(M_{1})$ other than $u$ or $v$. Next, since nodes in $V(M_{1})$ can only be
matched once in $M_{2}$, this limits the number of paths where $u$ and $v$ do
not participate in an augmenting path. This implies a large number of
augmenting paths in $M_{1}\cup M_{2}$ that are disjoint in their $V(M_{1})$
nodes. Finally, since each node in $\overline{V(M_{1})}$ belongs to at most
$b$ such paths, some large $\Omega(1/b)$ fraction of these augmenting paths
are also disjoint in their $\overline{V(M_{1})}$ nodes, from which we conclude
that $M_{1}\cup M_{2}$ contains a large set of node-disjoint augmenting paths
w.r.t. $M_{1}$, and that $G[M_{1}\cup M_{2}]$ contains a large matching.

We now substantiate the above intuition. The first lemma in this vein asserts
that $M_{1}\cup M_{2}$ contains many $3$-augmenting paths w.r.t. $M_{1}$
(assuming $M_{1}$ is not already near maximum in size).

######  Lemma 4.1.

If $|M_{1}|=\left(\frac{1}{2}+c\right)\cdot\mu(G)$, then $G[M_{1}\cup M_{2}]$
contains a set $\mathcal{P}$ of $3$-augmenting paths w.r.t. $M_{1}$ that are
disjoint in their $V(M_{1})$ nodes, with expected cardinality at least

$\mathbb{E}[|\mathcal{P}|]\geq\left(\frac{b}{b+1}\right)\cdot\left(\frac{1}{4}\cdot\left(\frac{1}{2}-3c\right)-\frac{1}{b}\cdot\left(\frac{1}{2}+c\right)-\frac{7\epsilon}{8}\right)\cdot\mu(G).$

As the proof of 4.1 is a little calculation heavy, we defer its proof to
Appendix C, and instead prove the following slightly weaker but simpler bound
here.

######  Lemma 4.2.

If $|M_{1}|=\left(\frac{1}{2}+c\right)\cdot\mu(G)$, then $G[M_{1}\cup M_{2}]$
contains a set $\mathcal{P}$ of $3$-augmenting paths w.r.t. $M_{1}$ that are
disjoint in their $V(M_{1})$ nodes, with expected cardinality at least

$\mathbb{E}[|\mathcal{P}|]\geq\left(\frac{1}{4}\cdot\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)-\frac{2}{b}\cdot\left(\frac{1}{2}+c\right)\right)\cdot\mu(G).$

###### Proof.

Fix a maximum set of node-disjoint $3$-augmenting paths in $G$ w.r.t. $M_{1}$,
denoted by $\mathcal{P}^{*}$. By 2.6, we have
$|\mathcal{P}^{*}|\geq\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)\cdot\mu(G)$.
Next, let $S\subseteq\mathcal{P}^{*}$ be the paths $u^{\prime}-u-v-v^{\prime}$
who “survive” the bipartition, in that $(u,u^{\prime}),(v,v^{\prime})\in
E_{2}$. By construction, each path in $\mathcal{P}^{*}$ survives with
probability exactly $\frac{1}{4}$. Therefore,
$\mathbb{E}[|S|]\geq\frac{1}{4}\cdot\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)\cdot\mu(G)$.

Now, for each survived path $u^{\prime}-u-v-v^{\prime}\in S$, either both $u$
and $v$ are matched (exactly once) in $M_{2}$, thus contributing an augmenting
path, or at least one of $u^{\prime}$ and $v^{\prime}$ must be matched in
$M_{2}$ to $b$ distinct nodes in $V(M_{1})$. But since each vertex in
$V(M_{1})$ is matched at most once in $M_{2}$, there are thus at most
$|V(M_{1})|/b=2|M_{1}|/b$ paths in $S$ whose middle edges do not belong to a
$3$-augmenting path in $M_{1}\cup M_{2}$. Therefore, there are at least
$|S|-2|M_{1}|/b$ many edges $(u,v)$ in $M_{1}$ whose endpoints are both
matched in $M_{2}$ to some (different) nodes $u^{\prime\prime}$ and
$v^{\prime\prime}$, respectively. Each such edge contributes an augmenting
path to a set $\mathcal{P}$ of the desired size,

$\displaystyle\mathbb{E}[|\mathcal{P}|]=\mathbb{E}[|S|]-\frac{2|M_{1}|}{b}$
$\displaystyle\geq\left(\frac{1}{4}\cdot\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)-\frac{2}{b}\cdot\left(\frac{1}{2}+c\right)\right)\cdot\mu(G).\qed$

The preceding two lemmas imply the existence of a multitude of $3$-augmenting
paths that are disjoint in their $V(M_{1})$ nodes. We now use these augmenting
paths to prove the existence of numerous (though possibly fewer) augmenting
paths that are disjoint in _all_ their nodes. Since each of the two
$\overline{V(M_{1})}$ nodes of a $3$-augmenting path belong to at most $b$
such paths, it is easy to find some $1/(2b-1)$ fraction of these augmenting
paths that are disjoint in all their nodes. The following lemma, resembling
[EHM16, Lemma 6], increases this fraction to $1/b$.

######  Lemma 4.3.

Let $\mathcal{P}$ be a set of $3$-augmenting paths w.r.t. $M_{1}$ in
$G[M_{1}\cup M_{2}]$ such that each $V(M_{1})$ (resp. $\overline{V(M_{1})}$)
node belongs to at most one (resp., $b$) paths in $\mathcal{P}$. Then
$\mathcal{P}$ contains a set of node-disjoint $3$-augmenting paths
$\mathcal{P}^{\prime}\subseteq\mathcal{P}$ of cardinality at least
$|\mathcal{P}^{\prime}|\geq\frac{1}{b}\cdot|\mathcal{P}|$.

###### Proof.

Consider the graph $G^{\prime}=(\overline{V(M_{1})},E^{\prime})$ obtained by
replacing each path $u^{\prime}-u-v-v^{\prime}$ in $\mathcal{P}$ with a single
edge $u^{\prime}-v^{\prime}$. This graph $G^{\prime}$ is bipartite, by virtue
of our random bipartition of $G$. Now, since this bipartite graph $G^{\prime}$
has maximum degree $b$, it contains a matching of size at least
$|E^{\prime}|/b=|\mathcal{P}|/b$: the fractional matching assigning values
$1/b$ to each edge has value $|E^{\prime}|/b$, and so $G^{\prime}$ contains an
_integral_ matching of at least the same value. On the other hand, disjoint
edges in $G^{\prime}$ have a one-to-one mapping to node-disjoint paths in
$\mathcal{P}$, since each node in $V(M_{1})$ belongs to at most one such path.
Thus, the maximum matching in $G^{\prime}$ corresponds to a collection
$\mathcal{P}^{\prime}\subseteq\mathcal{P}$ of node-disjoint augmenting paths
in $G[M_{1}\cup M_{2}]$ w.r.t. $M_{1}$, of cardinality at least
$|\mathcal{P}^{\prime}|\geq|\mathcal{P}|/b$. ∎

The three preceding lemmas imply that $G[M_{1}\cup M_{2}]$ contains a large
set of vertex-disjoint $3$-augmenting paths w.r.t. $M_{1}$, assuming this
latter matching is not already large. As we now show, this implies that
$G[M_{1}\cup M_{2}]$ contains a better-than-2-approximate matching.

######  Theorem 4.4.

Let $\epsilon\in(0,1/4)$. Then, Algorithm 2 with $b=9$ satisfies
$\mu(G)\geq\mathbb{E}[\mu(G[M_{1}\cup
M_{2}])]\geq\left(\frac{1}{2}+\frac{1}{144}-\epsilon\right)\cdot\mu(G)$, and
is thus
$(\frac{1}{2}+\frac{1}{144}-\epsilon)^{-1}<1.973(1+2\epsilon)$-approximate in
expectation.

###### Proof.

Let $|M_{1}|=\left(\frac{1}{2}+c\right)\cdot\mu(G)$, where
$c\in[-\epsilon/8,1/2]$, with the lower bound on $c$ following from 2.4 and
$M$ being an $(\epsilon/4)$-AMM. Let $\mathcal{P}^{\prime}$ be a maximum set
of vertex-disjoint $3$-augmenting paths w.r.t. $M_{1}$ in $G[M_{1}\cup
M_{2}]$. Then, augmenting along these paths, we find that
$M_{1}\bigoplus\mathcal{P}^{\prime}$ contains a matching (hence of size at
most $\mu(G)$) of the desired expected cardinality.

$\displaystyle\mathbb{E}[|M_{1}\bigoplus\mathcal{P}^{\prime}|]$
$\displaystyle=\mathbb{E}[|M_{1}|+|\mathcal{P}^{\prime}|]$
$\displaystyle\geq\left(\frac{1}{2}+c\right)\cdot\mu(G)+\left(\frac{1}{b+1}\cdot\left(\frac{1}{4}\cdot\left(\frac{1}{2}-3c\right)-\frac{1}{b}\cdot\left(\frac{1}{2}+c\right)-\frac{7\epsilon}{8}\right)\right)\cdot\mu(G)$
$\displaystyle\geq\left(\frac{1}{2}-\frac{\epsilon}{8}+\frac{1}{b+1}\cdot\left(\frac{1}{4}\cdot\frac{1}{2}-\frac{1}{b}\cdot\frac{1}{2}\right)-\frac{7\epsilon}{8}\right)\cdot\mu(G)$
$\displaystyle=\left(\frac{1}{2}+\frac{1}{144}-\epsilon\right)\cdot\mu(G).$

Above, the first inequality follows from 4.1 and 4.3, the second inequality
mainly relies on the parenthetical expression being increasing in
$c\geq-\epsilon/8$ (for our choice of $b=9$). Finally, the equality holds by
our choice of $b=9$. ∎

###  4.2 Dynamic Algorithms

In this section we provide the dynamic algorithms yielding our main results,
theorems 1.1 and 1.2. As with the bipartite case, our general approach is to
approximately implement our two-pass streaming algorithm in a dynamic setting.
Unlike the algorithm for bipartite graphs, here we need to (slightly) unbox
the sublinear-time algorithm of [Beh22] to find a large set of edges in
$M_{1}$ which belong to $3$-augmenting paths in $G[M_{1}\cup M_{2}]$, as
explained below.

####  4.2.1 Breaking the barrier of two in polylog time

In this section, we present a robust dynamic $(1.973+\epsilon)$-approximate
maximum matching size with worst case update time of
$t_{u}=\tilde{O}_{\epsilon}(1)$, and a query time of
$t_{q}=\tilde{O}_{\epsilon}(n)$, provided $\mu(G)\geq\epsilon n$. This,
combined with 2.1, implies our main result, 1.1.

For our dynamic (approximate) implementation of Algorithm 1, which works on
bipartite graphs, all we needed was to estimate $|M_{2}|$. In contrast, for
our dynamic (approximate) implementation of Algorithm 2, we will need to
estimate the size of the set $\mathcal{P}$ as guaranteed by 4.1. Specifically,
we note that the proofs of lemmas 4.1, and 4.3 and 4.4 imply the following
observation.

######  Observation 4.5.

Let $\widehat{M}_{1}\subseteq M_{1}$ be the set of edges in $M_{1}$ whose two
endpoints are matched in $M_{2}$ in Algorithm 2 run with $b=9$. Then,
$|M_{1}|+\frac{1}{b}\cdot\mathbb{E}\left[|\widehat{M}_{1}|\right]\geq\frac{\mu(G)}{1.973\cdot(1+2\epsilon)}$,
and also $\mu(G)\geq|M_{1}|+\frac{1}{b}\cdot|\widehat{M}_{1}|$.

To estimate $|\widehat{M}_{1}|$ efficiently, we make use of the following
extension of the algorithm of [Beh22].

######  Lemma 4.6.

Consider a graph $G^{\prime}=(V^{\prime},E^{\prime})$ with
$|V^{\prime}|=n^{\prime}$, and a matching $M$ with $V(M)\subseteq V^{\prime}$
that is not necessarily part of $G^{\prime}$ (i.e., we might have $M\nsubseteq
E^{\prime}$). For any matching $M^{\prime}$ in $G^{\prime}$, let
$k_{M^{\prime}}$ denote the number of edges in $M$ both of whose endpoints are
matched in $M^{\prime}$. There is an algorithm which, given adjacency matrix
query access to the edges of $G^{\prime}$, whp runs in
$\tilde{O}_{\epsilon}(n^{\prime})$ time and returns an estimate
$\kappa\in[k_{M^{\prime}}-\epsilon^{2}n^{\prime},k_{M^{\prime}}]$ for some
maximal matching $M^{\prime}$ in $G^{\prime}$.

This lemma follows from the work of [Beh22] rather directly, though it
requires some unboxing of the results there, due to the organization of that
work. We substantiate this lemma in Appendix B.

Given the above, we are now ready to prove the main result of this section,
which is summarized in the theorem below.

######  Theorem 4.7.

For any $\epsilon\in(0,1/4)$, there exists a robust dynamic matching size
estimator algorithm $\mathcal{A}$ with worst-case update time
$\tilde{O}_{\epsilon}(1)$ that, provided $\mu(G)\geq\epsilon\cdot n$, supports
$\tilde{O}_{\epsilon}(n)$-time queries and outputs a
$(1.973+\epsilon)$-approximate estimate w.h.p.

###### Proof.

The dynamic algorithm $\mathcal{A}$ is based on Algorithm 2. For its updates,
it maintains an $(\epsilon/4)$-AMM $M_{1}$ in the input graph $G$, using 2.5,
and a balanced binary search tree (BST) of edges in the graph, allowing for
logarithmic-time insertion, deletion and edge queries. This immediately
implies a worst-case update time of $t_{u}=\tilde{O}_{\epsilon}(1)$.

We now describe how Algorithm $\mathcal{A}$ responds to a query about the
maximum matching size. To answer this query, the algorithm considers a new
auxiliary graph $G^{*}=(V^{*},E^{*})$, which is defined as follows. For each
node $u\in V(M_{1})$, create a node $0_{u}$ in $G^{*}$. Next, for each node
$v\in\overline{V(M_{1})}$, create $b$ nodes $1_{v},\ldots,b_{v}$ in $G^{*}$.
Finally, for every edge $(u,v)\in E_{2}$, with $u\in V(M_{1})$ and
$v\in\overline{V(M_{1})}$, create an edge $(0_{u},i_{v})$ in $G^{*}$ for all
$i\in\\{1,\ldots,b\\}$. Note that there is a one-to-one mapping between
maximal matchings in the new graph $G^{*}$ and maximal $b$-matchings in $B$.

We emphasize that our dynamic algorithm $\mathcal{A}$ does not explicitly
maintain the auxiliary graph $G^{*}$. When we receive a query about the
maximum matching size in $G$, we explicitly construct only the node-set
$V^{*}$ of $G^{*}$, based on the matching $M_{1}$. This takes only $O(n)$
time. We can, however, simulate adjacency matrix queries in $G^{*}$
efficiently: there exists an edge $(0_{u},i_{v})$ in $G^{*}$ iff there exists
an edge $(u,v)$ between the corresponding nodes in $G$, verifiable in $O(\log
n)$ time using our edge-set BST.

At this point, we estimate the size of $\widehat{M}_{1}$ by invoking 4.6 with
$G^{\prime}=G^{*}$ and $M=M_{1}$. This gives us, in time
$\tilde{O}_{\epsilon}(n)$ a value $\kappa$ satisfying
$\kappa\in[|\widehat{M}_{1}|-\epsilon^{2}n,|\widehat{M}_{1}|]$, w.h.p. We now
return $\nu:=|M_{1}|+\frac{1}{b}\cdot\kappa$ as our estimate of $\mu(G)$. All
in all, our algorithm has query time $t_{q}=\tilde{O}_{\epsilon}(n)$.

It remains to analyze the approximation ratio. Towards this end, we observe
that, by our hypothesis that $\mu(G)\geq\epsilon\cdot n$,

$\displaystyle\mathbb{E}[\nu]$
$\displaystyle\geq\mathbb{E}\left[|M_{1}|+\frac{1}{b}\cdot(|\widehat{M}_{1}|-\epsilon^{2}n)\right]$
$\displaystyle=|M_{1}|+\frac{1}{b}\cdot\mathbb{E}\left[\widehat{M}_{1}\right]-\frac{\epsilon^{2}n}{b}$
$\displaystyle\geq\frac{\mu(G)}{1.973\cdot(1+2\epsilon)}-\epsilon^{2}n$
$\displaystyle\geq\frac{\mu(G)}{1.973\cdot(1+2\epsilon)}-\epsilon\cdot\mu(G)$
$\displaystyle\geq\frac{\mu(G)}{1.973\cdot(1+5\epsilon)}.$ (6)

In the above derivation, the second inequality follows from 4.5. Similarly, we
have whp:

$\displaystyle\nu$
$\displaystyle\leq|M_{1}|+\frac{1}{b}\cdot|\widehat{M}_{1}|\leq\mu(G).$ (7)

The second inequality in the above derivation again follows from 4.5. From (6)
and (7), we conclude that we return in response to each query a
$1.973(1+5\epsilon)$-approximation to $\mu(G)$ in expectation. Therefore, by
standard Chernoff bounds, running $O_{\epsilon}(\log n)$ copies of this
algorithm (increasing update and query time appropriately) and taking the
average of these will then result in a $1.973(1+O(\epsilon))$ approximation of
the desired value, w.h.p. Reparameterizing $\epsilon$ appropriately, the
theorem follows. ∎

Combined with 2.1, the above theorem implies our main result, 4.7.

####  4.2.2 New time/approximation tradeoffs

In this section we show our secondary result: a black-box method to improve
dynamic matching algorithm’s approximation ratio, at the cost of only
outputting a size estimate. We start with the following observation.

######  Proposition 4.8.

Let $G$ be an $n$-node graph, $\epsilon\in(0,1)$ and $\alpha\geq 1$. Then,
given an $\epsilon$-AMM $M^{\prime}$ and $\alpha$-approximate maximum matching
$M^{\prime\prime}$ in $G$, one can compute in $O(n)$ time a matching $M$ in
$G$ which is both $\alpha$-approximate and an $\epsilon$-AMM.

###### Proof.

The subgraph $G[M^{\prime}\cup M^{\prime\prime}]$ has maximum degree two, and
is thus the union of paths and cycles. Let $M$ be the matching obtained by
taking from each connected component $\mathcal{C}$ in $G[M^{\prime}\cup
M^{\prime\prime}]$ either the set of edges of $M^{\prime}$ or
$M^{\prime\prime}$ that are most plentiful in $\mathcal{C}$, breaking ties in
favor of $M^{\prime}$. By construction, it is clear that $M$ is a matching,
and that moreover $|M|\geq|M^{\prime\prime}|$, and so $M$ is
$\alpha$-approximate. On the other hand, $M$ matches all nodes of $M^{\prime}$
in each component, and therefore overall. That is, after removing at most
$\epsilon\mu(G)$ nodes in $V\setminus V(M)\subseteq V\setminus V(M^{\prime})$,
we obtain a graph in which $M$ is maximal. That is, the matching $M$ is also
an $\epsilon$-AMM. ∎

We are now ready to prove 1.2, restated below for ease of reference.

See 1.2

###### Proof.

Let $\epsilon>0$ be some sufficiently small constant. We describe how to
obtain a new dynamic matching size estimator $\mathcal{A}$ for $G$, with
update time $\tilde{O}_{\epsilon}(t_{u})$ that, provided
$\mu(G)\geq\epsilon\cdot n$, supports $\tilde{O}_{\epsilon}(n)$-time queries
and outputs a $\beta$-approximate estimate w.h.p., for some
$\beta=\alpha-\Omega((1-6(1/\alpha-1/2))^{2}))$. The theorem then immediately
follows from Proposition 2.1.

The algorithm $\mathcal{A}$ works as follows. It maintains an $\epsilon$-AMM
$M^{\prime}_{1}$, invoking Lemma 2.5, taking $\tilde{O}_{\epsilon}(1)$ update
time. It also maintains $\alpha$-approximate matching $M^{\prime\prime}_{1}$,
by running the dynamic algorithm guaranteed by the theorem’s hypothesis,
taking $t_{u}$ update time. Therefore, Algorithm $\mathcal{A}$ has an overall
update time of $t_{u}+\tilde{O}_{\epsilon}(1)=\tilde{O}_{\epsilon}(t_{u})$.

Upon receiving a query, Algorithm $\mathcal{A}$ first invokes Proposition 4.8
to obtain a matching $M_{1}$ (based on $M_{1}^{\prime}$ and
$M_{1}^{\prime\prime}$) that is simultaneously an $\epsilon$-AMM and an
$\alpha$-approximate maximum matching in $G$. This takes $O(n)$ time. The rest
of the query algorithm remains exactly the same as in Section 4.2. This
implies that Algorithm $\mathcal{A}$ has an overall query time of
$\tilde{O}_{\epsilon}(n)$.

We now analyze the approximation guarantee of $\mathcal{A}$. Towards this end,
observe that as $\alpha>1.5$, we can write $\frac{1}{\alpha}=\frac{1}{2}+c$
where $0<c<1/6$. So, we have that
$|M_{1}|=\left(\frac{1}{2}+z\right)\cdot\mu(G)$ for some $z\geq c$. Therefore,
by Lemma 4.2 and Lemma 4.2, there exists some set $\mathcal{P}^{\prime}$ of
node-disjoint length-three augmenting paths w.r.t. $M_{1}$ in $G[M_{1}\cup
M_{2}]$ whose cardinality satisfies

$\frac{|\mathcal{P}^{\prime}|}{\mu(G)}\geq
f_{b}(z):=\frac{1}{b}\cdot\left(\frac{1}{4}\cdot\left(\frac{1}{2}-3z-\frac{7\epsilon}{2}\right)-\frac{2}{b}\cdot\left(\frac{1}{2}+z\right)\right).$

Augmenting along these paths with respect to $M_{1}$, we obtain a new matching
in $G[M_{1}\cup M_{2}]$ of cardinality at least
$\left(\frac{1}{2}+z+f_{b}(z)\right)\cdot\mu(G)$. Now, for $b\geq 2$ (as we
will choose), this matching size is decreasing in $z$, as observed by taking
the derivative of $1/2+z+f_{b}(z)$ w.r.t. $z$. Therefore, the matching size is
minimized at $z=c$, and we find that $\mu(G[M_{1}\cup M_{2}])\geq
1/2+c+f_{b}(c)$. Taking another derivative, this time with respect to $b$, we
find that this expression is minimized (ignoring the $\epsilon$ dependence) at
$b^{*}=\frac{16(1+2c)}{1-6c}$. Note that $b\geq 16$, as $c\in(0,1/6)$. This
optimal $b^{*}$ need not be an integer, however, and so we take $b=\lceil
b^{*}\rceil\leq\frac{17}{16}b^{*}$ in our algorithm, and find that $M_{1}\cup
M_{2}$ contains a matching of size at least $\mu(G)$ times $1/2+z+f_{b}(z)\geq
1/2+c+f_{\frac{17b}{16}b^{*}}(c)\geq
1/2+c+\frac{9(1-6c)^{2}}{2312(1+2c))}-O(\epsilon/b)$. Moreover, some $b\cdot
f_{b}(z)$ many edges $\hat{M}_{1}\subseteq M_{1}$ have both of their endpoints
matched in the $b$-matching $M_{2}$.

We conclude that $\mathbb{E}[\mu(G[M_{1}\cup M_{2}])]$ gives a strictly-
better-than-$\alpha$ approximation to $\mu(G)$ (again using that $c<1/6$).
Specifically, the gain we get in the approximation ratio is of the order of
$\Theta((1-6c)^{2})=\Theta((1-6(1/\alpha-1/2))^{2})$. Now, using the fact that
$\mu(G)\geq\epsilon n$ and we are running the same query algorithm as in
Section 4.2, our estimation using the sub-linear-time algorithm (Lemma 4.6)
gives a strictly-better-than-$\alpha$ approximation to $\mu(G)$ in
expectation. As before, taking the average of $O(\log n)$ copies of this
algorithm will provide the same bound w.h.p., at an additional logarithmic
multiplicative overhead to the update and query times. ∎

######  Remark 4.9.

We note that the reduction underlying 1.2 preserves robustness and worst-case
update time.

##  5 AMMs against Adaptive Adversaries

In this section we prove 2.5. That is, we provide a robust dynamic algorithm
for maintaining an $\epsilon$-AMM in worst-case polylogarithmic update time.
But first, we motivate our algorithm, and characterize the kind of matching we
wish to compute.

We first recall a useful tool in the literature, namely _edge_ sparsification:
maintaining a sparse subgraph of $G$ containing a large matching–a so-called
_matching sparsifier_. Such sparsifiers naturally allow to achieve speedups in
the algorithms needed for 2.1, as a large matching in a sparsifier can be
computed quickly. One influential such sparsifier that we will use are
_kernels_ , introduced by Bhattacharya et al. [BHI18].

######  Definition 5.1.

For $\epsilon\geq[0,1]$ and $d\in\mathbb{N}$, a subgraph $K=(V,E_{K})$ of
graph $G=(V,E)$ is an _$(\epsilon,d)$ -kernel_ if $K$’s maximum degree is at
most $d$ and each edge $e\in E\setminus E_{K}$ has at least one endpoint of
degree at least $d(1-\epsilon)$ in $K$.

These sparsifiers will play an integral role in robustly and efficiently
maintaining an AMM in this section. We start by motivating their use in
computing AMMs in a _static_ setting.

###  5.1 From kernels to AMMs

To motivate the interest in bounded-degree graphs, we recall the following
observation, which follows from the $2\mu(G)$ endpoints of a maximum matching
forming a vertex cover (i.e., being incident on each edge of the graph.

######  Fact 5.2.

Let $G=(V,E)$ be a graph of maximum degree $\Delta$. Then $|E|\leq
2\mu(G)\cdot\Delta.$

Consequently, for small $d$ we have that $(\epsilon,d)$-kernels of $G$ are
sparse subgraphs. In particular, the time needed to compute maximal matchings
in such subgraphs is linear in their size, $|E_{K}|\leq 2\mu(K)\cdot
d=O(\mu(G)\cdot d)$. The following result of [DP14] implies that essentially
the same amount of time is needed to compute a _near-maximum-weight_ matching
in $K$.

######  Proposition 5.3.

Let $G=(V,E,w)$ be a weighted graph. Then, one can compute deterministically a
$(1+\epsilon)$-approximate maximum weight matching in $G$ in time
$O_{\epsilon}(|E|)$.

We now turn to identifying useful matchings in a kernel $K$ that allow us to
obtain an AMM of $G$. For this, we will need to upper bound the number of
high-degree nodes in $K$. Specifically, for an $(\epsilon,d)$-kernel $K$ of
graph $G$, we denote by $H_{K}:=\\{v\mid d_{K}(v)\geq d(1-\epsilon)\\}$ the
set of high-degree nodes in $K$. We will wish to argue that a removal of few
high-degree nodes in the kernel yields a subgraph in which our matching is
maximal. We therefore need to prove that the number of high-degree nodes is
itself small in terms of $\mu(G)$.

######  Lemma 5.4.

Let $K=(V,E_{K})$ be an $(\epsilon,d)$-kernel $K$ of $G$ with $\epsilon\leq
1/4$. Then $|H_{K}|\leq 4\mu(G)$.

###### Proof.

We consider the fractional matching $x\in\mathbb{R}^{E}$ where
$x_{e}=\mathds{1}[e\in E_{K}]/d$. By the degree bound of $K$, this is a
feasible fractional matching in $G$. Using this fractional matching, we can
show that

$\frac{1}{2}\cdot(1-\epsilon)\cdot|H_{K}|\leq\sum_{v\in H_{K}}\sum_{e\ni
v}x_{e}\leq\sum_{e}x_{e}\leq\frac{3}{2}\cdot\mu(G),$

where the first inequality follows from the definition of $H_{K}$ and possible
double counting of edges, and the last inequality follows from the integrality
gap of $\frac{3}{2}$ of the factional matching polytope. Simplifying the above
and using $\epsilon\leq 1/4$, we have that indeed
$|H_{K}|\leq(3/(1-\epsilon))\cdot\mu(G)\leq 4\mu(G)$. ∎

We now characterize the matchings that we wish to compute in this section,
prove that they exist and that they are AMMs.

######  Lemma 5.5.

Let $K=(V,E_{K})$ be an $(\epsilon,d)$-kernel of $G=(V,E)$, for
$\epsilon\in(0,1/4)$ and $d\geq\frac{1}{\epsilon}$. Then, a maximal matching
$M$ in $K$ that matches at least a $(1-c\cdot\epsilon)$-fraction of $H_{K}$ is
a $4c\epsilon$-AMM in $G$. Moreover, such a matching exists for $c=2$.

###### Proof.

First, we argue that such a matching $M$, if it exists, is indeed a
$4c\epsilon$-AMM in $G$. We recall that every edge in $E\setminus E_{K}$ has a
high-degree endpoint in $K$. Therefore, if we remove the $c\epsilon$ fraction
of high-degree nodes $H_{K}$ unmatched by $M$, each edge in $E\setminus E_{K}$
in the resulting graph $G^{\prime}$ has at least one endpoint matched in $M$.
On the other hand, every edge in $E_{K}$ has an endpoint matched in $M$, by
maximality of $M$ in $K$. We conclude that after removing
$c\epsilon\cdot|H_{K}|\leq 4c\epsilon\cdot\mu(G)$ nodes in $G$ (with the
inequality relying on 5.4), we obtain a graph $G^{\prime}$ where $M$ is
maximal. That is, $M$ is a $4c\epsilon$-AMM.

We now argue the existence of such a matching $M$ for $c=2$. Since $H$ has
maximum degree $d\geq\frac{1}{\epsilon}$, by Vizing’s theorem [Viz64] it can
be $(d+1)$-edge-colored, i.e., decomposed into $(d+1)$ matchings. A randomly-
chosen color in this edge coloring is a matching $M^{\prime}$ that matches
each edge with probability $\frac{1}{d+1}$, and thus it matches each high-
degree vertex $v$ with probability at least

$\Pr[v\textrm{
matched}]\geq(1-\epsilon)/(d+1)\geq(1-\epsilon)/(1+\epsilon)\geq 1-2\epsilon.$

Finally, extending this matching $M^{\prime}$ to also be maximal in $K$ by
adding edges of $K$ greedily then proves the existence of the desired
$8\epsilon$-AMM contained in the kernel $K$. ∎

The above implies a static algorithm with running time
$\tilde{O}_{\epsilon}(d\cdot\mu(G))$ for computing an $\epsilon$-AMM in $G$
given an $(\epsilon,d)$-kernel $K$ of $G$.

######  Lemma 5.6.

Given an $(\epsilon,d)$-kernel $K=(V,E_{K})$ of $G=(V,E)$, one can compute an
$\epsilon$-AMM in $G$ in deterministic time $O_{\epsilon}(d\cdot\mu(G))$.

###### Proof.

By 5.2, the number of edges in $K$ is at most $|E_{K}|=O(d\cdot\mu(G))$. We
then compute a $(1+\epsilon^{\prime})$-max weight matching $M^{\prime}$ in the
graph $G$ with edge weights equaling the number of high-degree nodes incident
on them, $w_{e}=\sum_{v\in e}\mathds{1}[v\in H_{K}]\in\\{0,1,2\\}$. By 5.3,
this can be done in deterministic time $O_{\epsilon}(d\cdot\mu(G))$. By 5.5,
this guarantees that at least a
$(1-2\epsilon^{\prime})/(1+\epsilon^{\prime})\geq(1-3\epsilon^{\prime})$
fraction of high-degree nodes in $K$ are unmatched by this dynamic subroutine.
We then extend $M^{\prime}$ to also be maximal in $K$, by scanning over the
$|E_{K}|=O(d\cdot\mu(G))$ edges of $K$ (in the same deterministic time) and
adding them to $M^{\prime}$ where possible. By 5.5, this results in a
$12\epsilon^{\prime}$-AMM, i.e., an $\epsilon$-AMM, after a total of
$O_{\epsilon}(d\cdot\mu(G))$ deterministic time. ∎

So far, we have provided a _static_ AMM algorithm with deterministic time
$O_{\epsilon}(d\cdot\mu(G))$, _provided we have access to a kernel_. To
dynamize the above, we fisrt show how to (periodically) compute a kernel
dynamically.

###  5.2 Periodic kernels and AMMs

In [Waj20], Wajc provided a method for rounding dynamic fractional matchings
to matching sparsifiers, and from these (by methods underlying Algorithm 3),
we can obtain integral matchings. Crucially for our needs, his framework was
robust, and allowed for worst-case update times. Unfortunately for us, the
lemma statements in his work do not immediately imply a robust dynamic kernel
maintenance. However, they do allow for _kernel queries_ , with running time
$\tilde{O}(d\cdot\mu(G))$.

######  Lemma 5.7.

Let $\epsilon\in(0,1)$ and $d=\tilde{O}_{\epsilon}(1)$ be sufficiently large.
Then, there exists a robust algorithm with worst-case update time
$t_{u}=\tilde{O}_{\epsilon}(1)$ allowing for $(\epsilon,d)$-kernel and
$\epsilon$-AMM queries in worst-case query time
$t_{q}=\tilde{O}_{\epsilon}(d\cdot\mu(G))$. The query’s outputs are a kernel
and an $\epsilon$-AMM w.h.p.

Given the ability to query a kernel, the ability to query an AMM then follows
directly from 5.6. As the proof and presentation of an algorithm allowing for
kernel queries essentially requires repeating verbatim numerous lemmas in
[Waj20], we defer its proof to Appendix D.

We now turn to designing a robust dynamic algorithm that _always_ maintains an
AMM.

###  5.3 Robust dynamic AMMs

So far, we have provided a method to answer AMM queries in a dynamic setting.
To lift this result to obtain AMM maintenance algorithms, we can rely on

######  Lemma 5.8.

Let $\epsilon\in(0,1/2)$. If $M$ is an $\epsilon$-AMM in $G$, then the non-
deleted edges of $M$ during any sequence of at most $\epsilon\cdot\mu(G)$
updates constitute a $6\epsilon$-AMM in $G$ (during the updates).

###### Proof.

Let $G$ and $M$ be the graph and matching before the updates, and let
$G^{\prime}$ and $M^{\prime}$ be their counterparts after these updates. Since
each update can decrease the size of the maximum matching size by at most one,
we have that

$\frac{1}{2}\cdot\mu(G)\leq(1-\epsilon)\cdot\mu(G)\leq\mu(G^{\prime}).$

Now, recall that for some set of vertices $U\subseteq V$ of size at most
$|U|\leq\epsilon\cdot\mu(G)$ nodes from $G$, the matching $M$ is maximal in
$G[V\setminus U]$. Now, after these $\epsilon\cdot\mu(G)$ updates, it might be
that $2\epsilon\cdot\mu(G)$ edges in $G^{\prime}$ are now not incident on
edges in $M^{\prime}$. (The factor of two arises due to edges of $M$ that are
deleted leaving two uncovered edges, addressable by removing two more nodes).
That is, after removing a node set $U^{\prime}\subseteq V$ of size at most
$|U^{\prime}|\leq 3\epsilon\cdot\mu(G)\leq 6\epsilon\cdot\mu(G^{\prime})$
nodes from $G^{\prime}$, we obtain a graph $G^{\prime}[V\setminus U^{\prime}]$
where $M^{\prime}$ is maximal. That is, $M^{\prime}$ is an $O(\epsilon)$-AMM
in $G^{\prime}$. ∎

The above “stability” property of AMMs again lends itself to the periodic re-
computation framework of [GP13], which, together with our algorithms for
querying for AMMs, yields algorithms for maintaining AMMs (always).

######  Lemma 5.9.

Let $\epsilon\in(0,1/2)$. Then, there exists a robust dynamic algorithm for
maintaining an $\epsilon$-AMM w.h.p. (at all times) in w.c. update time
$\tilde{O}_{\epsilon}(1)$.

###### Proof.

We will run the dynamic AMM query algorithm $\mathcal{A}$ of 5.7, whose update
fits within our update time budget. We will periodically query $\mathcal{A}$,
and spread this computation over these periods to guarantee low worst-case
update time. Specifically, we will divide the update sequence into _epochs_ ,
where if the graph $G$ at the start of epoch $i$ is $G_{i}$, then the epoch
has length $\ell_{i}\in[\epsilon\cdot\mu(G)/3,\epsilon\cdot\mu(G_{i})]$. In
order to determine the length of the epochs, we run the deterministic dynamic
$(2+\epsilon)$-approximate fractional matching algorithm of [BHN17], which in
particular gives us a $2+\epsilon\leq 3$-approximation of $\mu(G_{i})$ in
worst-case update time $\tilde{O}_{\epsilon}(1)$, again fitting within our
time budgets. Now, during phase $i$, we spend the time $t_{q}$ for the
$\epsilon$-AMM query subroutine of $\mathcal{A}$, so as to finish computing
$M_{i}$. The amount of time spent per update to achieve this goal is at most
$\frac{\tilde{O}_{\epsilon}(\mu(G_{i}))}{\lfloor\epsilon\cdot\mu(G_{i})/10\rfloor}=\tilde{O}_{\epsilon}(1),$
again fitting within our time updates. We now describe and analyze the
matchings maintained by this algorithm (these are not always $M_{i}$).

By 5.8, we need to provide a matching $M^{\prime}_{i+1}$ at the start of each
phase $i+1$ which is an $O(\epsilon)$-AMM in $G_{i+1}$, thus guaranteeing that
the non-deleted edges of $M^{\prime}_{i+1}$ remain an $O(\epsilon)$-AMM.
Reparameterizing appropriately will then yield the desired result. It remains
to define our matchings $M^{\prime}_{i}$. Using our estimate of $\mu(G)$
obtained by the dynamic fractional matching, we test whether
$\mu(G_{i})\in[1/\epsilon,10/\epsilon]$. If this is the case, then
$M^{\prime}_{i+1}$ is obtained by querying the AMM algorithm $\mathcal{A}$ at
the beginning of phase $i+1$, in time $O_{\epsilon}(1)$. (This relied on
$\mu(G_{i+1})\leq\mu(G_{i})+\ell_{i}\leq\mu(G_{i})\cdot(1+\epsilon)=\tilde{O}_{\epsilon}(1)$.)
By the properties of $\mathcal{A}$, the matching $M^{\prime}_{i+1}$ is an
$\epsilon$-AMM in $G_{i+1}$ w.h.p. Now, if conversely $\mu(G_{i})\geq
10/\epsilon$, then we have that

$\frac{1}{2}\cdot\mu(G_{i})\leq(1-\epsilon)\cdot\mu(G_{i})\leq\mu(G_{i})-\ell_{i}\leq\mu(G_{i+1}).$

Now, $M_{i}$, is an $\epsilon$-AMM in $G_{i}$, which is obtained from
$G_{i+1}$ by at most $\epsilon\cdot\mu(G_{i})\leq 2\epsilon\cdot\mu(G_{i+1})$
updates. Therefore, by 5.8 $M_{i}$ is a $12\epsilon$-AMM in $G_{i+1}$. We
therefore take $M^{\prime}_{i+1}$ to be $M_{i}$. Reparameterizing $\epsilon$
appropriately, the lemma follows. ∎

##  6 Conclusion and Future Directions

We presented the first dynamic matching (size estimation) algorithm breaking
the approximation barrier of $2$ in polylogarithmic update time. While this
presents a major advance in our understanding of the dynamic matching problem,
many questions remain. We mention a few such questions which we find
particularly intriguing.

##### Explicit Fast Matching.

In our work we show how to maintain a better-than-two approximate estimate of
the maximum matching size. Can one also maintain an explicit matching of
similar approximation ratio within the same time bounds?

##### Better approximation in $o(n)$ update time?

Known conditional impossibility results rule out an exact algorithm with
$n^{1-\Omega(1)}$ update time [AVW14, HKNS15, Dah16], but the best
approximation ratios currently known are $\frac{3}{2}+\epsilon$ [BS15, BS16,
Kis22, GSSU22]. Can one do better in $o(n)$ time? On the flip side, can we
show any (conditional) hardness of _approximate_ dynamic matching, for any
approximation ratio?

##### Unconditional impossibility results.

With this work we bring dynamic matching with better-than-two approximation
into the polylogarithmic update time regime—the range where _unconditional_
impossibility are known for numerous data structures and dynamic algorithms.
Can such unconditional impossibility results be proven for (approximate)
dynamic matching?

##### Acknowledgements.

We thank the anonymous reviewers for helpful comments.

## APPENDIX

##  Appendix A Proofs of basic building blocks

Here we substantiate some key propositions implied by prior work. We stress
that we provide proofs mostly for completeness, due to our propositions being
slight variants or being differently organized than their previous
counterparts. That is, we do not claim novelty of the underlying ideas of this
section.

###  A.1 Proof of Proposition 2.1

A key component of 2.1 is the following vertex sparsification technique for
dynamic settings by Kiss [Kis22], adapted from such a vertex sparsification of
Assadi et al. [AKLY16] in the context of stochastic matching.

######  Proposition A.1.

There exists a randomized algorithm which for each update to $G$ makes an
update to $O\left(\frac{\log^{2}n}{\epsilon^{3}}\right)$ contracted subgraphs,
such that w.h.p. throughout any (possibly adaptively generated) update
sequence, one subgraph $G^{\prime}$ has a matching of cardinality
$\mu(G)\cdot(1-O(\epsilon))$ and nodeset of size
$n^{\prime}\leq\mu(G)/\epsilon$. Moreover, any matching $M^{\prime}$ in
$G^{\prime}$ can be transformed into a matching in $G$ of cardinality
$|M^{\prime}|$ in time $O(|M^{\prime}|)$. For any matching $M^{\prime}$ in any
$G^{\prime}$ undergoing edge updates we can maintain a matching of cardinality
$|M^{\prime}|$ in $G$ with $O(1)$ worst-case update time.

###### Proof.

Consider a random graph $G^{\prime}$ obtained by hashing each node into one of
$k/\epsilon$ buckets, for some integer $k$, and contracting all nodes that are
hashed into the same bin. That is, two contracted nodes neighbor in
$G^{\prime}$ if their corresponding bins contain neighboring nodes in $G$. By
storing for each edge $e$ in $G^{\prime}$ a list of edges inducing $e$, we can
easily transform a matching $M^{\prime}$ in $G^{\prime}$ to a matching in $G$
of the same cardinality in time $O(|M^{\prime}|)$. The majority of this proof
is thus dedicated to showing that $O\left(\frac{\log n}{\epsilon^{2}}\right)$
such contractions for each value $k=\lceil(1+\epsilon)^{i}\rceil$ with
$i\in[\log_{1+\epsilon}(n)]\subseteq\left[O\left(\frac{\log
n}{\epsilon}\right)\right]$ suffice to guarantee that one of these
$G^{\prime}$ contains a matching of cardinality at least
$\mu(G)\cdot(1-3\epsilon)$.

Fix an integer $i$ and $k=\lceil(1+\epsilon)^{i}\rceil\leq n$. Fix a matching
$M$ in $G$ of cardinality $|M|\leq k$. The probability that a vertex $v$
incident on some edge of $M$ is contracted into a separate bin than the other
$2|M|-1$ endpoints can be expressed as follows:

$(1-1/(k/\epsilon-1))^{2|M|-1}\geq\left(1-\frac{2\cdot\epsilon}{k}\right)^{2\cdot
k}\geq(1-5\cdot\epsilon).$

Thus, by linearity, the number $X$ of such endpoints of edges of $M$ satisfy
that $\mathbb{E}[X]\geq(1-5\epsilon)\cdot 2|M|$. Observe that $X$ is the sum
of negatively associated random variables, by [DR98], since the hashing of
vertices is equivalent to the folklore balls and bins experiment, so by
standard Chernoff Bounds,

$\Pr[X\leq
2\cdot|M|\cdot(1-6\epsilon)]\leq\exp\left(-\Theta(\epsilon^{2}|M|)\right).$

If at least $2|M|\cdot(1-6\cdot\epsilon)$ endpoints of $M$ are hashed to
unique vertices then at least $|M|-2|M|\cdot
6\epsilon\geq|M|\cdot(1-12\epsilon)$ edges of $M$ had both of their endpoints
assigned to unique vertices in $G^{\prime}$ hence are present in $G^{\prime}$.

We say that the contraction is _bad_ if for _some_ matching $M$ of cardinality
in the range $[k,k(1+\epsilon)+1]$ if the number of edges of $M$ that are not
present in $G^{\prime}$ is lesser than $|M|\cdot(1-12\epsilon)$. Otherwise, it
is _good_. Now, there are $\sum_{i=k}^{k(1+\epsilon)+1}{n\choose i}\leq
k\epsilon\cdot n^{k(1+\epsilon)+1}\leq n^{k(1+\epsilon)+2}$ possible matchings
of size $|M|\in[k,k(1+\epsilon)]$. Therefore, by randomly contracting the
graph for range $[k,k(1+\epsilon)+1]$ some $\frac{C\log n}{\epsilon^{2}}$ many
times, for a sufficiently large $C$, we have that the probability that all
contractions for range $[k,k(1+\epsilon)+1]$ are bad is

$\displaystyle\Pr[\textrm{all contractions are bad}]$ $\displaystyle\leq
n^{k(1+\epsilon)+2}\cdot\exp\left(-\Theta(\epsilon^{2}k)\cdot\frac{C\log
n}{\epsilon^{2}}\right)\leq n^{-3}.$

Therefore, taking union bound over the $\log_{1+\epsilon}(n)$ possible value
of $k$, we find that with high probability, each range $[k,k(1+\epsilon)+1]$
has some good contraction.

We conclude that, w.h.p., among the
$O\left(\frac{\log^{2}n}{\epsilon^{3}}\right)$ contracted graphs, there exists
a good contraction for every $k=\lceil(1+\epsilon)^{i}\rceil$, and in
particular for $k\leq\mu(G)\leq k(1+\epsilon)+1$. That is, one of the
contracted graphs contains a large matching,
$\mu(G^{\prime})\geq\mu(G)\cdot(1-12\epsilon)$, and has few nodes,
$n^{\prime}\leq k/\epsilon\leq\mu(G)/\epsilon$, as desired. ∎

We now proceed towards proving 2.1, restated below for ease of reference. See
2.1

###### Proof.

Let $\epsilon^{\prime}=\alpha^{\prime}\cdot\epsilon\cdot 2$ (here
$\alpha^{\prime}$ is some $O(1)$ factor). Using the algorithm described by A.1
we can generate $T=\tilde{O}_{\epsilon}(1)$ graphs $G_{i}:i\in[T]$ with the
following properties: A) $\mu(G_{i})\leq\mu(G)$ for all $i\in[T]$, B) There is
an $i\in[T]$ satisfying that $\mu(G_{i})\geq(1-\epsilon^{\prime})\cdot\mu(G)$
and $\mu(G_{i})\geq n\cdot\epsilon^{\prime}$, C) All sub-graphs $G_{i}$
undergo a single update when $G$ undergoes an update.

Our algorithm proceeds as follows: on all $T$ generated sub-graphs we run
algorithm $\mathcal{A}$ at all times. Furthermore, on each sub-graph we
maintain an $O(1)=\alpha^{\prime}$-approximate estimate on the maximum
matching size $\tilde{\mu_{i}}$ using algorithms from literature (randomized
against an adaptive adversary) in $\tilde{O}_{\epsilon}(1)$ worst-case time.
For all sub-graphs we monitor the relationship of $\tilde{\mu_{i}}$ and
$|V_{i}|$. If $\tilde{\mu_{i}}$ increases above the threshold of
$|V_{i}|\cdot\epsilon$ we start a run of the query algorithm on $G_{i}$
returning us an $\alpha$-approximate estimate of $\mu(G_{i})$ which will
define $\nu_{i}^{\prime}$. We distribute the work of this query over
$|V_{i}|\cdot(\epsilon)^{2}$ updates and re-initiate the query every
$|V_{i}|\cdot(\epsilon)^{2}$ updates. The matching size queries of $G_{i}$
always run on the state of $G_{i}$ at the start of the query (even though
$G_{i}$ undergoes updates during it’s run). If $\tilde{\mu}_{i}$ decreases
bellow the threshold of $|V_{i}|\cdot\epsilon$ we stop the querying process
and set $\nu_{i}^{\prime}=0$. Note that at initialization we just set
$\nu_{i}^{\prime}=\mu(G_{i})$ for all $i\in[T]$ statically.

At all times we maintain the output $\max_{i\in R}\nu_{i}^{\prime}$, the
maximum of our matching size estimates.

Algorithm 3 Vertex set sparsification

1: Initialize $\nu_{i}^{\prime}=\mu(G_{i})$

2: Maintain contracted sub-graphs $G_{i}$ and $\alpha^{\prime}$-approximate
matching size estimates $\tilde{\mu}_{i}$

3: Run algorithm $\mathcal{A}$ on every $G_{i}$

4: for $i\in[T]$ do

5: if $\tilde{\mu}_{i}$ becomes at least $|V_{i}|\cdot\epsilon$ then

6: Initiate a matching size query of $G_{i}$ in $O(t_{q})$ time on the current
state of $G_{i}$

7: Distribute the work over the next $|V_{i}|\cdot\epsilon^{2}$ updates

8: Repeatedly recompute distributed over every $|V_{i}|\cdot\epsilon^{2}$
updates

9: Let $\nu_{i}^{\prime}$ be the latest finished estimate

10: if $\tilde{\mu}_{i}$ reduces below $|V_{i}|\cdot\epsilon$ then

11: Terminate the querying process of $\mu(G_{i})$

12: Set $\nu_{i}^{\prime}\leftarrow 0$

13: At all times return $\max_{i\in[T]}\nu_{i}^{\prime}$

We first discuss the update time of Algorithm 3. The maintenance of the $T$
contracted sub-graphs and matching size estimates $\tilde{\mu}_{i}$ takes
$\tilde{O}_{\epsilon}(1)$ w.c. time. Running algorithm $\mathcal{A}$ on each
of the contracted sub-graphs takes update time $\tilde{O}_{\epsilon}(t_{u})$
(and is worst case if $\mathcal{A}$ has worst-case update time). A matching
size query will only be initiated and run on contracted sub-graph $G_{i}$ if
$\tilde{\mu}_{i}\geq\mu(G_{i})/\alpha^{\prime}\geq|V_{i}|\cdot\epsilon$, that
is if $\mu(G_{i})\geq|V_{i}|\cdot\epsilon/2$. Each re-computation of the
estimate $\nu_{i}^{\prime}$ will be distributed over some
$|V_{i}|\cdot\epsilon^{2}$ updates, that is, it will take
$O(t_{q}/(|V_{i}|\cdot\epsilon^{2})=O_{\epsilon}(t_{q}/|V_{i}|)$ worst-case
time. Finding and returning the maximum matching size estimate
$\nu_{i}^{\prime}$ takes $\tilde{O}_{\epsilon}(1)=O(T)$ time. Therefore, the
total update time of the algorithm is
$\tilde{O}_{\epsilon}(t_{u}+t_{q}\cdot\beta/n)$ and is worst-case if
$\mathcal{A}$ has worst-case update time. Furthermore, all components of the
algorithm but $\mathcal{A}$ are randomized against an adaptive adversary..

It remains to argue that the algorithm maintains $\nu^{\prime}$ such that
$\nu^{\prime}\leq\mu(G)\leq\nu^{\prime}\cdot(\alpha+O(\epsilon))$ at all
times. Say that $G_{i}$ is a ’successful’ contraction if $G_{i}$ satisfies
property B). By A.1, w.h.p., there is a successful contraction at all times,
at time point $\tau_{1}$ let that contraction be $G_{i}$. We will separate two
instances:

i) Throughout the run of the algorithm at all times it held that
$\tilde{\mu}_{i}\geq|V_{i}|\cdot\epsilon$: The algorithm has ran the matching
size query sub-routine on $G_{i}$ after every $|V_{i}|\cdot\epsilon^{2}$ edge
updates. Let $G^{\tau_{0}}_{i}$ be the past state of the graph $G_{i}$ when
the algorithm started calculating the current estimate
$(\nu^{\tau_{1}}_{i})^{\prime}$. By the scheduling of this calculation we know
that $\tau_{0}\geq\tau_{1}-\epsilon^{2}\cdot|V_{i}|$. Hence,
$\mu(G^{\tau_{0}}_{i})\geq\mu(G^{\tau_{1}}_{i})-\epsilon^{2}\cdot|V_{i}|$,
where $\mu(G^{\tau_{1}}_{i})\geq\mu(G)\cdot(1-\epsilon^{\prime})$ and
$\mu(G^{\tau_{1}}_{i})\geq|V|_{i}\cdot\epsilon^{\prime}$. Hence,
$(\nu^{\tau_{1}}_{i})^{\prime}\cdot\alpha\cdot(1+O(\epsilon))\geq\mu(G)$.

ii) At time $\tau_{1}$ $G_{i}$ is a successful contraction but at some prior
point during the run of the algorithm $\tilde{\mu}_{i}$ became less than
$|V_{i}|\cdot\epsilon$: we know that at some point $\tau_{0}$ prior to
$\tau_{1}$ $\tilde{\mu}_{i}$ must have increased above $|V_{i}|\cdot\epsilon$.
Define the state of $G_{i}$ at the two time points as $G^{\tau_{0}}_{i}$ and
$G^{\tau_{1}}_{i}$ respectively. As at $\tau_{1}$ $G^{\tau_{1}}_{i}$ is a
successful contraction we know that
$\mu(G^{\tau_{1}}_{i})\geq|V_{i}|\cdot\epsilon^{\prime}$. When
$\tilde{\mu}_{i}$ crossed the threshold at $\tau_{0}$ it held that
$\tilde{\mu}_{i}=|V_{i}|\cdot\epsilon$ that is
$\mu(G_{i}^{\tau_{0}})_{i}\leq|V_{i}|\cdot\epsilon\cdot\alpha$. As per each
update the maximum matching size may only change by $1$ we have that
$\tau_{1}-\tau_{0}\geq|V_{i}|\cdot\epsilon\cdot\alpha$. Hence, by time
$\tau_{1}$ the algorithm already had an updated estimate of $\nu_{i}^{\prime}$
(that is one calculated in the previous $\epsilon^{2}\cdot|V_{i}|$ updates
such that $\mu(G_{i})\geq|V_{i}|\cdot\epsilon$ during these updates). Here we
can refer back to the previous case (pretending the algorithm initialized at
$\tau_{0}$). ∎

###  A.2 Proof of Proposition 2.6

We now give a proof extending standard arguments that small maximal matchings
contain many length-three augmenting paths to showing that small
$\epsilon$-AMM likewise contain many such paths.

See 2.6

###### Proof.

The above bound for $\epsilon=0$ is well-known (see, e.g., [KMM12]). We reduce
to this case by removing the at most $\epsilon\cdot\mu(G)$ nodes in
$V\setminus V(M)$ needed to make $M$ maximal. This yields a graph $G^{\prime}$
with $\mu(G^{\prime})\geq\mu(G)\cdot(1-\epsilon)$, and therefore

$|M|\leq\left(\frac{1}{2}+c\right)\cdot\mu(G)\leq\frac{\frac{1}{2}+c}{1-\epsilon}\cdot\mu(G^{\prime})\leq\left(\frac{1}{2}+c+\epsilon\right)\cdot\mu(G^{\prime}),$

Consequently, by the special case of this proposition with $\epsilon=0$, we
have that the maximum number of disjoint 3-augmenting paths that $M$ admits in
$G^{\prime}$ (and hence also in $G$) is at least

$\displaystyle\left(\frac{1}{2}-3(c+\epsilon)\right)\cdot\mu(G^{\prime})$
$\displaystyle\geq\left(\frac{1}{2}-3(c+\epsilon)\right)(1-\epsilon)\cdot\mu(G)\geq\left(\frac{1}{2}-3(c+\epsilon)-\frac{\epsilon}{2}\right)\cdot\mu(G).\qed$

##  Appendix B Proof of Lemma 4.6

Our proof of Lemma 4.6 is a minor modification of the argument from Section 5
of [Beh22]. We claim no novelty for this proof. To make our notations
consistent with the ones used by [Beh22], we will focus on an $n$-node graph
$G=(V,E)$ (different from our dynamic input graph). Let $\pi$ be a permutation
of the edges of graph $G=(V,E)$. Let $GMM(G,\pi)$ stand for the output of the
greedy maximum matching algorithm when run on graph $G$ with edge ordering
$\pi$.

###  B.1 Building blocks

B.1 is explicitly concluded by [Beh22], whereas B.2 is a slight modification
of a construction appearing in Section 5 of [Beh22] we need to fit our
arguments.

######  Lemma B.1.

There is a randomized algorithm that in $\tilde{O}(|E|/|V|)$ expected time
returns the matched status of a random $v$ under $GMM(G,\pi)$, for random
$\pi$. This algorithm relies on list access to the edges of $G$.

In order to prove 4.6 we have to work with adjacency matrix queries. Based on
a slight modification of Section 5 of [Beh22] we can derive the following tool
for this purpose.

######  Lemma B.2.

Let $\delta\in(0,1/2)$. For a given $n$-node graph $G=(V,E)$ there exists a
supergraph $H=(V_{H},E_{H})$ of $G$ (i.e., $V_{H}\supseteq V$ and
$E_{H}\supseteq E$) satisfying the following:

  * •

$|E_{H}|=\Theta_{\delta}(n^{2})$.

  * •

$|V_{H}|=\Theta_{\delta}(n^{2})$.

  * •

At most $\delta\cdot n$ nodes of $V$ are matched to nodes in $V_{H}\setminus
V$ by $GMM(H,\pi)$, w.h.p. over $\pi$.

  * •

$GMM(H,\pi)\cap E$ is a maximal matching in $G[V\setminus V_{slack}]$, where
$V_{slack}\subseteq V$ are nodes in $V$ that are matched to nodes in
$V\setminus V_{H}$.

  * •

Any adjacency list query to $E_{H}$ (querying the $i$-th neighbour of a vertex
according to some ordering of neighbours) can be implemented using one
adjacency matrix query to $E$ (querying the existence of any edge $(u,v)$).

Informally, the main change in our construction compared to that of [Beh22] is
that our construction will allow us to argue that the random matching in the
constructed graph $H$ is, w.h.p., a maximal matching after ignoring a small
set of nodes. In contrast, the construction in [Beh22] resulted in an
“expected” version of this guarantee. As the high-probability bounds will
simplify our discussion later, we modify this construction below. The second
change we make is in externalizing the fact that the matching computed this
way is maximal, rather than 2-approximate, as stated in [Beh22]. We now turn
to proving the above lemma.

###### Proof of B.2.

The node-set of $H$ is $V_{H}:=V\cup
V^{*}\cup(W_{1}\ldots,W_{n})\cup(U_{1},\ldots,U_{n})$, where
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$ (note that $G=(V,E_{H}[V])$),
$V^{*}=\\{v^{*}_{2},v^{*}_{2},\ldots,v^{*}_{2}\\}$,
$W_{i}=\\{w^{1}_{i},w^{2}_{i},\ldots w^{n}_{i}\\}$, and the set
$U_{i}=\\{u^{1}_{i},u^{2}_{i},\ldots,u^{s}_{i}\\}$ is of size $s:=10n/\delta$
for all $i\in[n]$. To specify the edge-set $E_{H}$, we now define the ordered
adjacency list for every node $v\in V_{H}$.

  * •

Every node $v_{i}\in V$ has degree exactly $n$: For any $j\in[n]$, if
$(v_{i},v_{j})\in E$ then the $j^{th}$ neighbor of $v_{i}$ is the node
$v_{j}\in V$, otherwise it is the node $v^{*}_{j}\in V^{*}$.

  * •

Every node $v^{*}_{i}\in V^{*}$ has degree exactly $n+s$: For any $j\in[n]$,
if $(v_{i},v_{j})\in E$ then the $j^{th}$ neighbor of $v^{*}_{i}$ is the node
$w^{j}_{i}\in W_{i}$, otherwise it is the node $v_{j}\in V$. Furthermore, for
all $j\in[s]$, the $(n+j)^{th}$ neighbor of $v^{*}_{i}$ is the node
$u^{j}_{i}\in U_{i}$.

  * •

Each node in $U_{j}$, for any $j\in[n]$, has only one neighbor (which is
$v^{*}_{j}$).

  * •

Node $w^{j}_{i}$ may have degree at most one: if $(v_{i},v_{j})\in E$ then
$w^{j}_{i}$ is a neighbour of $v^{*}_{i}\in V^{*}$, otherwise it is an
isolated vertex of $H$.

Note that $|V_{H}|=2n+n^{2}+ns=\Theta(n^{2}/\delta)$ and that similarly
$|E_{H}|=n^{2}+|E|+ns=\Theta(n^{2}/\delta)$. Furthermore, from the above
discussion it is immediate that an adjacency list query to $E_{H}$ (i.e.,
querying for the $j$-th neighbor of a vertex) can be implemented using at most
one adjacency matrix query to $E$. It remains to prove the remaining two
properties of $H$.

To this end, recall that $V_{slack}$ denotes the set of vertices in $V$
matched to $V$* nodes. Then, by maximality of $GMM(H,\pi)$, we have that
$GMM(H,\pi)\cap E$ is indeed maximal matching of $G[V\setminus V_{slack}]$. We
now turn to bound $|V_{slack}|$. To this end, we say a node $v^{*}\in V^{*}$
is occupied if its earliest edge in $\pi$ has its other endpoint in $W_{i}$ or
$U_{i}$. Trivially, such an occupied vertex $v^{*}\in V^{*}$ is matched to a
vertex of $U_{v^{*}}\cup W_{v^{*}}$ under $GMM(H,\pi)$. The following simple
claim, which follows by a Chernoff bound together with the simple observation
that it is unlikely for a node in $V*$ to be matched in $V$ (and thus
contribute to $|V_{slack}|$).

######  Claim B.3.

Let $\pi$ be a uniformly random permutation of $E_{H}$. Let
$X_{v^{*}}:v^{*}\in V^{*}$ represent the indicator variable of $v^{*}$ being
occupied and $X_{O}=\sum X_{v^{*}}$. Then $X\geq n\cdot(1-\delta)$ w.h.p.

###### Proof.

Note that each $v^{*}\in V^{*}$ has at most $n$ edges with vertices of
$V^{\prime}$ and has at least $10n/\delta$ edges with vertices in $U_{v^{*}}$
and $W_{v^{*}}$. Therefore,

$\mathbb{E}[X_{v^{*}}]=\Pr(X_{v^{*}}=1)\geq\frac{n\cdot
10/\delta}{n\cdot(10/\delta+1)}=1-\frac{1}{10/\delta+1}\geq 1-\delta/10.$

On the other hand, the variables $\\{X_{v^{*}}\mid v\in V\\}$ are independent
binary variables. Therefore, by Chernoff’s bound, we have that

$\displaystyle\Pr(X_{O}\leq n\cdot(1-\delta))$ $\displaystyle\leq$
$\displaystyle\Pr\left(X_{O}\leq
n\cdot(1-\delta/10)-\frac{n\cdot\delta}{2}\right)$ (8) $\displaystyle\leq$
$\displaystyle\Pr\left(X_{O}\leq\mathbb{E}[X_{O}]-\mathbb{E}[X_{O}]\cdot\frac{\delta}{2}\right)$
$\displaystyle\leq$ $\displaystyle
2\cdot\exp\left(-\frac{(\delta/2)^{2}\cdot\mathbb{E}[X_{O}]}{3}\right)$ (9)
$\displaystyle\leq$ $\displaystyle n^{-\Theta(1)}$ (10)

Inequality 8 follows from the fact that $n\geq E[X_{O}]\geq n\cdot(1-\delta)$.
Inequality 9 is an application of Chernoff’s bound. Inequality 10 follows as
long as $n\cdot\delta^{2}\in\Omega(\log(n))$. ∎

The above claim completes the proof of the last requirement of Lemma B.2. ∎

###  B.2 The algorithm

We now introduce the algorithm that will build on the previous two lemmas and
inform the proof of 4.6, given in Algorithm 4. Recall that we wish to estimate
the number of edges in some input matching, which here, to avoid confusion, we
denote by $M^{*}$, that are both matched in some maximal matching in $G$.

Let $H=(V_{H},E_{H})$ be the supergraph of $G$ defined by B.2 of $G$ with
$\delta=\epsilon^{2}/8$. For a permutation $\pi$ of $E_{H}$, define
$M^{\prime}(\pi):=\text{GMM}(H,\pi)\cap(V\times V)$ to be the set of edges in
$\text{GMM}(H,\pi)$ both of whose endpoints are in $V$. Let $M(\pi)$ be a
maximal matching in $G$ that is obtained by augmenting $M^{\prime}(\pi)$,
i.e., we start with $M=M^{\prime}(\pi)$, visit the edges $e\in E$ in an
arbitrarily fixed order, and obtain the matching $M(\pi)$ by greedily adding
as many edges to $M$ as possible. Note that $M^{\prime}(\pi)\subseteq
M(\pi)\subseteq E^{\prime}$. Note also that $M(\pi)$ will be the maximal
matching that 4.6 refers to as $M^{\prime}$. We now slightly overload our
notations and let $k_{M^{\prime}(\pi)}$ denote the number of edges in $M^{*}$
both of whose endpoints are matched in $M^{\prime}(\pi)$.777Recall that in the
statement of 4.6 we defined the notation $k_{M^{\prime}}$ only if $M^{\prime}$
is a matching in $G^{\prime}$, which is not the case with $M^{\prime}(\pi)$.
Nevertheless, for ease of exposition, we use the notation
$k_{M^{\prime}(\pi)}$.

Algorithm 4 Extended Sub-Linear Algorithm

1: if $|M^{*}|\leq\epsilon^{2}\cdot n$ then

2: Return $\kappa=0$

3: (Implicitly) construct $H=(V_{H},E_{H})$ as in B.2 with
$\delta=\epsilon^{2}/8$

4: Sample a permutation $\pi$ of $E_{H}$ uniformly at random

5: $L\leftarrow\frac{10^{5}\cdot\log(n)}{\epsilon^{5}}$

6: Sample $L$ edges $e_{1},\dots,e_{L}\in M^{*}$ uniformly at random with
replacement

7: Let $X_{i}$ be one if both endpoints of edge $e_{i}$ are matched by
$GMM(H,\pi)$ and $X=\sum_{i}X_{i}$

8: Return $\kappa=\frac{X\cdot|M|}{L}-\frac{n\cdot\epsilon^{2}}{2}$

######  Claim B.4.

Algorithm 4 can be implemented in time $\tilde{O}_{\epsilon}(n)$ in
expectation.

###### Proof.

The construction of $H$ is implicit, and as such takes no time. Let
$T_{H}(v,\pi)$ stand for the time it takes to calculate the matched status of
vertex $v\in V_{H}$ in $GMM(H,\pi)$ using the algorithm of [BK22]. By Lemma
B.1 we have that $\underset{v\sim
V_{H}}{\mathbb{E}}[T_{H}(v,\pi)]=\tilde{O}_{\epsilon}(|E_{H}|/|V_{H}|)=\tilde{O}_{\epsilon}(1)$.
Therefore, since the endpoints of the sampled edges
$S=\bigcup_{i=1}^{L}{e_{i}}\subseteq V_{H}$ are a subset of of vertices of
cardinality $|S|\geq\epsilon^{2}\cdot n$, and since
$|V_{H}|=\Theta_{\epsilon}(n^{2})$ we have the expected time to calculate
their matched status (using adjacency matrix queries, using the construction
of $H$) is

$\displaystyle\underset{v\sim S}{\mathbb{E}_{H}}[T_{H}(v,\pi)]$
$\displaystyle\leq\underset{v\sim
V_{H}}{\mathbb{E}}[T_{H}(v,\pi)]\cdot\frac{|V_{H}|}{|S|}\leq\tilde{O}_{\epsilon}(n)\qed$

We now argue that Algorithm 4 provides a good approximation of the number of
nodes in $M^{*}$ both of whose endpoints are matched by $GMM(H,\pi)$. But
first, we recall the basic Chernoff bounds that we will rely on here.

######  Lemma B.5.

Chernoff bound: Let $X$ be the sum of independently distributed (or negatively
associated) random variables $X_{1},\dots,X_{m}$ with $X_{i}\in[0,1]$ for each
$i\in[m]$. Then for all $\delta\in(0,1)$:

$\Pr(|X-E[X]|\geq\delta\cdot E[X])\leq 2\cdot\exp\left(-\frac{\delta^{2}\cdot
E[X]}{3}\right).$

######  Lemma B.6.

W.h.p., The output $\kappa$ of Algorithm 4 satisfies

$\kappa_{M(\pi)}\geq\kappa\geq\kappa_{M(\pi)}-n\cdot\epsilon^{2}.$

###### Proof.

First, by B.2, we have that w.h.p., the set of nodes $V_{slack}\subseteq V$
that are matched to nodes in $V_{H}\setminus V$ have cardinality at most
$|V_{slack}|\leq n\epsilon^{2}/8$. Moreover, $GMM(H,\pi)\cap E$ is a maximal
matching in $G[V\setminus V_{slack}]$.

Observe that whenever $\kappa=0$ is returned by the algorithm due to $|M^{*}|$
being small, the algorithm returns a trivially correct solution. As
$M^{\prime}(\pi)$ is an $\epsilon^{2}/8$-AMM, we conclude that:

$|M^{\prime}(\pi)|\leq|M(\pi)|\leq|M^{\prime}(\pi)|+\frac{n\cdot\epsilon^{2}}{8}.$
(11)

Define $M^{*}_{H}$ to be the set of edges of $M^{*}$ such that both of their
endpoints are matched by $GMM(H,\pi)$. By the guarantees of the construction
of $H$ we know that there can be at most $n\cdot\epsilon^{2}/8$ vertices of
$V$ matched by an edge not in $M^{\prime}(\pi)$. Therefore,

$|M^{*}_{H}|\geq\kappa_{M^{\prime}(\pi)}\geq|M^{*}_{H}|-\frac{n\cdot\epsilon^{2}}{8}.$
(12)

Note that using the Algorithm 4 is sampling from edges of $M^{*}$ and
determining if they are in $M^{*}_{H}$ (hence approximating
$\kappa_{M^{*}_{H}}$). Specifically, by inequalities (11) and (12), we get the
following.

$\displaystyle\kappa_{M^{*}_{H}}$
$\displaystyle\in\left[\kappa_{M^{\prime}(\pi)}\pm\frac{n\cdot\epsilon^{2}}{8}\right]\subseteq\left[\kappa_{M(\pi)}\pm\frac{n\cdot\epsilon^{2}}{8}\pm|M(\pi)|-|M^{\prime}(\pi)|\right]\subseteq\left[\kappa_{M(\pi)}\pm\frac{n\cdot\epsilon^{2}}{4}\right].$

We will argue that with high probability
$\frac{X\cdot|M|}{L}\in\left[\kappa_{M^{*}_{H}}\pm\frac{n\cdot\epsilon^{2}}{8}\right]$,
dependent on the randomization of $M^{*}_{L}$. Observe that $X_{i}$ are
independently distributed random variables taking values in $[0,1]$ and $X$ is
a binomial variable with parameters $k,|\kappa_{M^{*}_{H}}|/|M|$. We will
consider two cases:

Case (A): $\kappa_{M^{*}_{H}}\leq\frac{n\cdot\epsilon^{3}}{8}$. In this case,
we derive that

$\displaystyle\Pr\left(\frac{X\cdot|M|}{L}\notin\left[\kappa_{M^{*}_{H}}\pm\frac{n\cdot\epsilon^{2}}{8}\right]\right)$
$\displaystyle=$
$\displaystyle\Pr\left(\frac{X\cdot|M|}{L}\geq\kappa_{M^{*}_{H}}+\frac{n\cdot\epsilon^{2}}{8}\right)$
(13) $\displaystyle\leq$
$\displaystyle\Pr\left(\frac{X\cdot|M|}{L}\geq\frac{n\cdot\epsilon^{2}}{8}\right)$
$\displaystyle=$
$\displaystyle\Pr\left(B(L,\kappa_{M^{*}_{H}}/|M|)\geq\frac{n\cdot\epsilon^{2}}{8}\right)$
$\displaystyle\leq$
$\displaystyle\Pr\left(B(L,\epsilon)\geq\frac{n\cdot\epsilon^{2}}{8}\right)$
$\displaystyle\leq$ $\displaystyle\Pr\left(B(L,\epsilon)\geq
2\cdot\mathbb{E}[B(L,\epsilon)]\right)$ $\displaystyle\leq$ $\displaystyle
2\cdot\exp\left(-\frac{\mathbb{E}[B(L,\epsilon)]}{3}\right)$
$\displaystyle\leq$ $\displaystyle n^{-\Theta(1)}.$

In the above derivation, (13) holds as $\kappa_{M^{*}_{H}}/|M|\leq\epsilon$
(as otherwise $\kappa=0$ would have been returned by the algorithm), and (B.2)
is true assuming $n\cdot\epsilon^{2}/8\geq 2\cdot
L\cdot\epsilon=\tilde{O}(1)$. Finally, (B.2) follows from Chernoff bound
(Lemma B.5) on a binomial random variable.

Case (B): $\kappa_{M^{*}_{H}}\geq n\cdot\frac{\epsilon^{3}}{8}$. In this case,
we derive that

$\displaystyle\Pr\left(\frac{X\cdot|M|}{L}\notin\left[\kappa_{M^{*}_{H}}\pm\frac{n\cdot\epsilon^{2}}{8}\right]\right)$
$\displaystyle=$
$\displaystyle\Pr\left(|X-E[X]|\geq\frac{n\cdot\epsilon^{2}}{8}\cdot\frac{L}{|M|}\right)$
(16) $\displaystyle=$
$\displaystyle\Pr\left(|X-\mathbb{E}[X]|\geq\mathbb{E}[X]\cdot\frac{n\cdot\epsilon^{2}}{8\cdot\kappa_{M^{*}_{H}}}\right)$
$\displaystyle\leq$
$\displaystyle\Pr\left(|X-\mathbb{E}[X]|\geq\mathbb{E}[X]\cdot\frac{n\cdot\epsilon^{2}}{8\cdot
n}\right)$ $\displaystyle\leq$ $\displaystyle
2\cdot\exp\left(-\frac{\left(\epsilon^{2}/8\right)^{2}\cdot\mathbb{E}[X]}{3}\right)$
$\displaystyle=$
$\displaystyle\exp\left(-\frac{L\cdot\kappa_{M^{*}_{H}}\cdot\epsilon^{4}}{|M|\cdot
194}\right)$ $\displaystyle\leq$ $\displaystyle n^{-\Theta(1)}.$

In the above derivation, (16) follows from Chernoff bound (Lemma B.5), and
(B.2) holds due to on our assumptions on $|M|$ and $\kappa_{M^{*}_{H}}$.
Therefore, with high probability
$X\cdot|M|/k\in[\kappa_{M^{*}_{H}}\pm\epsilon^{2}\cdot
n/8]\in[\kappa_{M(\pi)}\pm\epsilon^{2}\cdot n\cdot(1/8+1/4)]$ (recall that
$\kappa_{M(\pi)}=\kappa_{M}$). This implies that
$\kappa\leq\kappa_{M}+\epsilon^{2}\cdot n\cdot(1/8+1/4-1/2)\leq\kappa_{M}$ and
$\kappa\geq\kappa_{M}-\epsilon^{2}\cdot
n\cdot(1/8+1/4-1/2)\geq\kappa_{M}-\epsilon^{2}\cdot n$. ∎

Having concluded that Algorithm 4 can be implement in low expected time, and
is correct w.h.p., we are now ready to prove 4.6, restate below for ease of
reference. (Note that here $G=(V,E)$ are renamed
$G^{\prime}=(V^{\prime},E^{\prime})$, and $n^{\prime}$ and $k_{M^{\prime}}$
correspond respectively to $n$ and $\kappa_{M(\pi)}$, whereas $M^{*}$ in
Algorithm 4 is renamed $M$.)

See 4.6

###### Proof.

By B.4, Algorithm 4 runs in expected $\tilde{O}_{\epsilon}(n)$ time and
returns a correct solution with high probability. To improve its running time
guarantee to a high probability bound we only need to incur a blowup of
$O(\log(n))$ in running time: run the algorithm $O(\log(n))$ time in parallel
and output the solution given by the first terminating copy. One of these
algorithms will terminate within at most twice the expected time, by Markov’s
inequality, and so w.h.p., one of these completes after
$\tilde{O}_{\epsilon}(n)$ time. Finally, by union bound and B.6, all of the
$\log n$ algorithms’ output satisfies the desired bounds with probability
$1-1/poly(n)$, and so w.h.p., we obtain a solution satisfying the desired
bounds after $\tilde{O}_{\epsilon}(n)$ time. ∎

##  Appendix C Omitted Proofs from Section 4.1

Here we prove the tighter bound on the number of $V(M_{1})$-disjoint
$3$-augmenting paths in the subgraph $M_{1}\cup M_{2}$ as output by Algorithm
2, restated below. See 4.1

###### Proof.

Fix a maximum set of disjoint length-three augmenting paths w.r.t. $M_{1}$ in
$G$, denoted by $\mathcal{P}^{*}$. By 2.6, we have
$|\mathcal{P}^{*}|\geq\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)\cdot\mu(G)$.
Next, let $S\subseteq\mathcal{P}^{*}$ be the paths $u^{\prime}-u-v-v^{\prime}$
that “survive” the bipartition, in the sense that
$(u,u^{\prime}),(v,v^{\prime})\in E_{2}$. By construction, each path in
$\mathcal{P}^{*}$ survives with probability exactly $\frac{1}{4}$. Therefore,
$\mathbb{E}[|S|]\geq\frac{1}{4}\cdot\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)\cdot\mu(G)$.
Let $D:=\mathcal{P}^{*}\setminus S$ be the set of paths that did not survive
this bipartition.

For $i\in\\{0,1,2\\}$, let $S_{i}\subseteq S$ and $D_{i}\subseteq D$ be the
sets of paths $u^{\prime}-u-v-v^{\prime}$ in $S$ and $D$ (respectively) with
$i$ of their $V(M_{1})$ nodes $u$ and $v$ matched in $M_{2}$. Now, by our
bipartition, if $u^{\prime}-u-v-v^{\prime}\in S_{2}\cup D_{2}$, i.e., if $u$
and $v$ are both matched in $M_{2}$, then they are matched to distinct nodes.
Therefore, $G[M_{1}\cup M_{2}]$ contains a set of augmenting paths
$\mathcal{P}$ w.r.t. $M_{1}$ that are disjoint in their $V(M_{1})$ nodes, of
cardinality $|\mathcal{P}|=|S_{2}|+|D_{2}|$. We now turn to lower bounding
$|S_{2}|+|D_{2}|$.

To bound $|S_{2}|+|D_{2}|$, we will double count the edges of $M_{2}$, once
from their $V(M_{1})$ endpoints, and once from their $\overline{V(M_{1})}$
endpoints. First, by definition, since each edge in $M_{2}$ has exactly one
endpoint in $V(M_{1})$ and each node in $V(M_{1})$ is matched at most once in
$M_{2}$, we have that
$|M_{2}|=2|S_{2}|+|S_{1}|+2|D_{2}|+|D_{1}|\leq|S_{2}|+|D_{2}|+|M_{1}|,$ where
the inequality follows from $|M_{1}|\geq\sum_{i=0}^{2}(|S_{i}|+|D_{i}|)$, by
definition. On the other hand, for each of the $|S|-|S_{2}|=|S_{0}|+|S_{1}|$
survived paths $u^{\prime}-u-v-v^{\prime}\in S_{0}\cup S_{1}$ that does not
have both its internal nodes matched in $M_{2}$, we have by maximality of
$M_{2}$ that $u^{\prime}$ and/or $v^{\prime}$ must contribute $b$ distinct
edges to $M_{2}$. Therefore, $|M_{2}|\geq b\cdot(|S_{0}|+|S_{1}|)$. Combining
the above, we obtain

$\displaystyle b\cdot(|S|-|S_{2}|)\leq|M_{2}|\leq|S_{2}|+|D_{2}|+|M_{1}|,$

which after rearranging, yields

$\displaystyle
b\cdot|S|-|M_{1}|\leq(b+1)\cdot|S_{2}|+|D_{2}|\leq(b+1)\cdot(|S_{2}|+|D_{2}|).$

Simplifying and combining with the lower bound on $\mathbb{E}[|S|]$, we obtain
the claimed bound, as follows.

$\displaystyle\mathbb{E}[|\mathcal{P}|]=\mathbb{E}[|S_{2}|+|D_{2}|]$
$\displaystyle\geq\frac{b}{b+1}\cdot\left(\mathbb{E}[|S|]-\frac{1}{b}\cdot|M_{1}|\right)$
$\displaystyle\geq\frac{b}{b+1}\cdot\left(\frac{1}{4}\cdot\left(\frac{1}{2}-3c-\frac{7\epsilon}{2}\right)-\frac{1}{b}\cdot\left(\frac{1}{2}+c\right)\right)\cdot\mu(G).$
$\displaystyle=\frac{b}{b+1}\cdot\left(\frac{1}{4}\cdot\left(\frac{1}{2}-3c\right)-\frac{1}{b}\cdot\left(\frac{1}{2}+c\right)-\frac{7\epsilon}{8}\right)\cdot\mu(G).\qed$

##  Appendix D Omitted Proofs of Section 5

We stress that the following is essentially implied by the work of [Waj20],
from which we now repeat significant amount of text essentially verbatim. The
only difference here will be our final proof of 5.7, allowing us to
efficiently periodically compute an $\epsilon$-AMM, and the use of this lemma
in the subsequent section. Readers familiar with [Waj20] are encourage to read
ahead to that lemma.

##### Overview.

Briefly, [Waj20] identified an edge-coloring-based approach to compute, based
on the efficient maintenance of edge colorings and a particular fractional
matching of [BHI18], a kernel. (See Algorithm 5.) We start by recalling the
type of fractional matching needed here, due to [ACC+18].

######  Definition D.1.

For $c\geq 1$ and $d\geq 1$, a fractional matching $\vec{x}$ is _$(c,d)$
-approximately-maximal $(c,d)$-AMfM_ if every edge $e\in E$ either has
fractional value $x_{e}>1/d$ or it has one endpoint $v$ with $\sum_{e\ni
v}x_{e}\geq 1/c$ with all edges $e^{\prime}$ incident on this $v$ having value
$x_{e^{\prime}}\leq 1/d$.

As proven in [ACC+18, Appendix A], the dynamic fractional matching of [BHN17]
is precisely such an approximately-maximal matching.

######  Lemma D.2.

For all $\epsilon\leq\frac{1}{2}$, there is a deterministic dynamic
$(1+2\epsilon,\max\\{54\log n/\epsilon^{3},(3/\epsilon)^{21}\\})$-AMfM
algorithm with $t_{u}=O(\log^{3}n/\epsilon^{7})$ worst-case update time,
changing at most $O(\log n/\epsilon^{2})$ edges’ fractions per update in the
worst case.

Now, we turn to the sparsification procedure of [Waj20], given in Algorithm 5.
Briefly, this algorithm decomposes the graph into a logarithmic number of
subgraphs, based on grouped $x$-values, edge colors these subgraphs using at
most $\gamma=2$ times their maximum degree, and then outputs the union of
these subgraphs.

Algorithm 5 Edge-Color and Sparsify [Waj20]

1: for $i\in\\{1,2,\dots,\lceil 2\log_{1+\epsilon}(n/\epsilon)\rceil\\}$ do

2: let $E_{i}\triangleq\\{e\mid
x_{e}\in((1+\epsilon)^{-i},(1+\epsilon)^{-i+1}]\\}$.

3: compute a $2\lceil(1+\epsilon)^{i}\rceil$-edge-coloring $\chi_{i}$ of
$G_{i}\triangleq G[E_{i}]$. $\rhd$ Note: $\Delta(G_{i})<(1+\epsilon)^{i}$

4: Let $S_{i}$ be a sample of $\min\\{2\lceil
d(1+\epsilon)\rceil,2\lceil(1+\epsilon)^{i}\rceil\\}$ colors without
replacement in $\chi_{i}$.

5: Return $K\triangleq(V,\bigcup_{i}\bigcup_{M\in S_{i}}M)$.

The following lemma of [Waj20] allows us to compute kernels from AMfMs using
Algorithm 5.

######  Lemma D.3.

Let $c\geq 1$, $\epsilon>0$ and $d\geq\frac{9c(1+\epsilon)^{2}\cdot\log
n}{\epsilon^{2}}$. If $\vec{x}$ is a $(c,d)$-AMfM, then the subgraph $K$
output by Algorithm 5 when run on $\vec{x}$ with $\epsilon$ and $d$ is a
$(c(1+O(\epsilon),d(1+O(\epsilon),0)$-kernel, w.h.p.

We are now ready to prove our (periodic) algorithmic kernel and AMM
algorithm’s guarantees, restated below for ease of reference.

See 5.7

###### Proof.

We maintain the dynamic $(1+2\epsilon,\tilde{O}_{\epsilon}(1))$-AMfM of D.2,
using $\tilde{O}_{\epsilon}(1)$ deterministic w.c. update time and number of
changes to edges per update. In addition, we maintain the subgraphs $G_{i}$ in
Algorithm 5. In each such subgraph we maintain
$2\lceil(1+\epsilon)^{i}\rceil$-color edge colorings in each $G_{i}$ in
$O(\log n)$ deterministic w.c. time per change to $\vec{x}$, using the
logarithmic-time $(2\Delta-1)$-edge coloring algorithm of [BCH20]. This
concludes the description of the updates, which by the above take
deterministic w.c. update time $t_{u}=\tilde{O}_{\epsilon}(1)$.

Next, to compute a kernel, we run the sampling step of Algorithm 5. As this is
bottlenecked by the time to write down the $O(\log^{2}n)$ colors (matchings),
each of size no greater than $\mu(G)$ (by definition), this query takes
deterministic $\tilde{O}(\mu(G))$. Finally, this output graph $K$ is an
$(O(\epsilon),d(1+O(\epsilon))$-kernel w.h.p., by D.3. Finally, to output an
$\epsilon$-AMM, we appeal to the static algorithm 5.6, which runs in
deterministic time $\tilde{O}_{\epsilon}(d\cdot\mu(G))=\tilde{O}(\mu(G))$ and
outputs an $\epsilon$-AMM, provided $K$ is a kernel, i.e., it also succeeds
w.h.p. ∎

## References

  * [ACC+18] Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, and David Wajc.  Dynamic matching: Reducing integral algorithms to approximately-maximal fractional algorithms.  In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), pages 79:1–79:16, 2018.
  * [AD16] Amir Abboud and Søren Dahlgaard.  Popular conjectures as a barrier for dynamic planar graph algorithms.  In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 477–486, 2016.
  * [AG13] Kook Jin Ahn and Sudipto Guha.  Linear programming in the semi-streaming model with application to the maximum matching problem.  Information and Computation, 222:59–79, 2013.
  * [AJJ+22] Sepehr Assadi, Arun Jambulapati, Yujia Jin, Aaron Sidford, and Kevin Tian.  Semi-streaming bipartite matching in fewer passes and optimal space.  In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 627–669, 2022.
  * [AKL19] Sepehr Assadi, Sanjeev Khanna, and Yang Li.  The stochastic matching problem with (very) few queries.  ACM Transactions on Economics and Computation (TEAC), 7(3):1–19, 2019.
  * [AKLY16] Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev.  Maximum matchings in dynamic graph streams and the simultaneous communication model.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1345–1364, 2016.
  * [AVW14] Amir Abboud and Virginia Vassilevska Williams.  Popular conjectures imply strong lower bounds for dynamic problems.  In Proceedings of the 55th Symposium on Foundations of Computer Science (FOCS), pages 434–443, 2014.
  * [BCH20] Sayan Bhattacharya, Deeparnab Chakrabarty, and Monika Henzinger.  Deterministic dynamic matching in ${O}(1)$ update time.  Algorithmica, 82(4):1057–1080, 2020.
  * [BDH+19] Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan.  Fully dynamic maximal independent set with polylogarithmic update time.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pages 382–405, 2019.
  * [BDL21] Aaron Bernstein, Aditi Dudeja, and Zachary Langley.  A framework for dynamic matching in weighted graphs.  In Proceedings of the 53rd Annual ACM Symposium on Theory of Computing (STOC), 2021.
  * [Beh22] Soheil Behnezhad.  Time-optimal sublinear algorithms for matching and vertex cover.  In Proceedings of the 62nd Symposium on Foundations of Computer Science (FOCS), pages 873–884, 2022.
  * [Beh23] Soheil Behnezhad.  Dynamic algorithms for maximum matching size.  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), page To appear in, 2023.
  * [BFH19] Aaron Bernstein, Sebastian Forster, and Monika Henzinger.  A deamortization approach for dynamic spanner and dynamic maximal matching.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1899–1918, 2019.
  * [BGS15] Surender Baswana, Manoj Gupta, and Sandeep Sen.  Fully dynamic maximal matching in ${O}(\log n)$ update time.  SIAM Journal on Computing (SICOMP), 44(1):88–113, 2015.
  * [BHI18] Sayan Bhattacharya, Monika Henzinger, and Giuseppe F Italiano.  Deterministic fully dynamic data structures for vertex cover and matching.  SIAM Journal on Computing (SICOMP), 47(3):859–887, 2018.
  * [BHN16] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  New deterministic approximation algorithms for fully dynamic matching.  In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), pages 398–411, 2016.
  * [BHN17] Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai.  Fully dynamic approximate maximum matching and minimum vertex cover in ${O}(\log^{3}n)$ worst case update time.  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 470–489, 2017.
  * [BK19] Sayan Bhattacharya and Janardhan Kulkarni.  Deterministically maintaining a $(2+\epsilon)$-approximate minimum vertex cover in ${O}(1/\epsilon^{2})$ amortized update time.  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1872–1885, 2019.
  * [BK21] Sayan Bhattacharya and Peter Kiss.  Deterministic rounding of dynamic fractional matchings.  In Proceedings of the 48th International Colloquium on Automata, Languages and Programming (ICALP), 2021.
  * [BK22] Soheil Behnezhad and Sanjeev Khanna.  New trade-offs for fully dynamic matching via hierarchical edcs.  In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3529–3566, 2022.
  * [BKM+22] Amos Beimel, Haim Kaplan, Yishay Mansour, Kobbi Nissim, Thatchaphol Saranurak, and Uri Stemmer.  Dynamic algorithms against an adaptive adversary: Generic constructions and lower bounds.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 1671–1684, 2022.
  * [BLM20] Soheil Behnezhad, Jakub Łącki, and Vahab Mirrokni.  Fully dynamic matching: Beating 2-approximation in ${\Delta}^{\epsilon}$ update time.  In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2492–2508, 2020.
  * [BNS19] Jan van den Brand, Danupon Nanongkai, and Thatchaphol Saranurak.  Dynamic matrix inverse: Improved algorithms and matching conditional lower bounds.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pages 456–480, 2019.
  * [BS15] Aaron Bernstein and Cliff Stein.  Fully dynamic matching in bipartite graphs.  In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), pages 167–179, 2015.
  * [BS16] Aaron Bernstein and Cliff Stein.  Faster fully dynamic matchings with small approximation ratios.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 692–711, 2016.
  * [CK19] Julia Chuzhoy and Sanjeev Khanna.  A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems.  In Proceedings of the 51st Annual ACM Symposium on Theory of Computing (STOC), pages 389–400, 2019.
  * [CS14] Michael Crouch and Daniel M Stubbs.  Improved streaming algorithms for weighted matching, via unweighted matching.  In Proceedings of the 17th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), page 96, 2014.
  * [CS18] Moses Charikar and Shay Solomon.  Fully dynamic almost-maximal matching: Breaking the polynomial barrier for worst-case time bounds.  In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP), pages 33:1–33:14, 2018.
  * [CZ19] Shiri Chechik and Tianyi Zhang.  Fully dynamic maximal independent set in expected poly-log update time.  In Proceedings of the 60th Symposium on Foundations of Computer Science (FOCS), pages 370–381, 2019.
  * [Dah16] Søren Dahlgaard.  On the hardness of partially dynamic graph problems and connections to diameter.  In Proceedings of the 43rd International Colloquium on Automata, Languages and Programming (ICALP), pages 48:1–48:14, 2016.
  * [DP14] Ran Duan and Seth Pettie.  Linear-time approximation for maximum weight matching.  Journal of the ACM (JACM), 61(1):1, 2014.
  * [DR98] Devdatt P. Dubhashi and Desh Ranjan.  Balls and bins: A study in negative dependence.  Random Struct. Algorithms, 13(2):99–124, 1998.
  * [Edm65a] Jack Edmonds.  Maximum matching and a polyhedron with 0, 1-vertices.  Journal of research of the National Bureau of Standards B, 69(125-130):55–56, 1965.
  * [Edm65b] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of mathematics, 17(3):449–467, 1965.
  * [EHM16] Hossein Esfandiari, MohammadTaghi Hajiaghayi, and Morteza Monemizadeh.  Finding large matchings in semi-streaming.  In 2016 IEEE 16th International Conference on Data Mining Workshops (ICDMW), pages 608–614, 2016.
  * [EKS09] Sebastian Eggert, Lasse Kliemann, and Anand Srivastav.  Bipartite graph matchings in the semi-streaming model.  In Proceedings of the 16th Annual European Symposium on Algorithms (ESA), pages 492–503, 2009.
  * [ELSW13] Leah Epstein, Asaf Levin, Danny Segev, and Oren Weimann.  Improved bounds for online preemptive matching.  In Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), page 389, 2013.
  * [FKM+05] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.  On graph problems in a semi-streaming model.  Theoretical Computer Science (TCS), 348(2-3):207–216, 2005.
  * [FMP+18] Matthew Fahrbach, Gary L Miller, Richard Peng, Saurabh Sawlani, Junxing Wang, and Shen Chen Xu.  Graph sketching against adaptive adversaries applied to the minimum degree algorithm.  In Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS), pages 101–112, 2018.
  * [FMU22] Manuela Fischer, Slobodan Mitrović, and Jara Uitto.  Deterministic $(1+\epsilon)$-approximate maximum matching with poly $(1/\epsilon)$ passes in the semi-streaming model and beyond.  In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC), pages 248–260, 2022.
  * [FS22] Moran Feldman and Ariel Szarf.  Maximum matching sans maximal matching: A new approach for finding maximum matchings in the data stream model.  In Proceedings of the 25th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2022\.
  * [GKK09] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  Perfect matchings in ${O}(n^{1.5})$ time in regular bipartite graphs.  arXiv preprint arXiv:0902.1617, 2009.
  * [GKK10] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  Perfect matchings via uniform sampling in regular bipartite graphs.  ACM Transactions on Algorithms (TALG), 6(2):27, 2010.
  * [GKK12] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  On the communication and streaming complexity of maximum bipartite matching.  In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 468–485, 2012.
  * [GKK13] Ashish Goel, Michael Kapralov, and Sanjeev Khanna.  Perfect matchings in ${O}(n\log n)$ time in regular bipartite graphs.  SIAM Journal on Computing (SICOMP), 42(3):1392–1404, 2013.
  * [GP13] Manoj Gupta and Richard Peng.  Fully dynamic $(1+\epsilon)$-approximate matchings.  In Proceedings of the 54th Symposium on Foundations of Computer Science (FOCS), pages 548–557, 2013.
  * [GSSU22] Fabrizio Grandoni, Chris Schwiegelshohn, Shay Solomon, and Amitai Uzrad.  Maintaining an edcs in general graphs: Simpler, density-sensitive and with worst-case time bounds.  Proceedings of the 5th Symposium on Simplicity in Algorithms (SOSA), pages 12–23, 2022.
  * [GW19] Mohsen Ghaffari and David Wajc.  Simplified and space-optimal semi-streaming $(2+\epsilon)$-approximate matching.  In Proceedings of the 2nd Symposium on Simplicity in Algorithms (SOSA), 2019.
  * [HKNS15] Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak.  Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture.  In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pages 21–30, 2015.
  * [Kap13] Michael Kapralov.  Better bounds for matchings in the streaming model.  In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1679–1697, 2013.
  * [Kap21] Michael Kapralov.  Space lower bounds for approximating maximum matching in the edge arrival model.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1874–1893, 2021.
  * [Kis22] Peter Kiss.  Improving update times of dynamic matching algorithms from amortized to worst case.  Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 94:1–94:21, 2022.
  * [KMM12] Christian Konrad, Frédéric Magniez, and Claire Mathieu.  Maximum matching in semi-streaming with few passes.  In Proceedings of the 15th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 231–242, 2012.
  * [KN21] Christian Konrad and Kheeran K Naidu.  On two-pass streaming algorithms for maximum bipartite matching.  In Proceedings of the 24th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 19:1–19:18, 2021.
  * [Kon18] Christian Konrad.  A simple augmentation method for matchings with applications to streaming algorithms.  In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 2018.
  * [KPP16] Tsvi Kopelowitz, Seth Pettie, and Ely Porat.  Higher lower bounds from the 3sum conjecture.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1272–1287, 2016.
  * [KT17] Sagar Kale and Sumedh Tirodkar.  Maximum matching in two, three, and a few more passes over graph streams.  In Proceedings of the 20th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2017\.
  * [Kuh55] Harold W Kuhn.  The hungarian method for the assignment problem.  Naval research logistics quarterly, 2(1-2):83–97, 1955.
  * [LMSVW22] Hung Le, Lazar Milenković, Shay Solomon, and Virginia Vassilevska Williams.  Dynamic matching algorithms under vertex updates.  In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022.
  * [McG05] Andrew McGregor.  Finding graph matchings in data streams.  In Proceedings of the 8th International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 170–181. 2005.
  * [NO08] Huy N Nguyen and Krzysztof Onak.  Constant-time approximation algorithms via local improvements.  In Proceedings of the 49th Symposium on Foundations of Computer Science (FOCS), pages 327–336, 2008.
  * [NS17] Danupon Nanongkai and Thatchaphol Saranurak.  Dynamic spanning forest with worst-case update time: adaptive, las vegas, and ${O}(n^{1/2-\varepsilon})$-time.  In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC), pages 1122–1129, 2017.
  * [OR10] Krzysztof Onak and Ronitt Rubinfeld.  Maintaining a large matching and a small vertex cover.  In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 457–464, 2010.
  * [ORRR12] Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld.  A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.  In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1123–1131, 2012.
  * [PR07] Michal Parnas and Dana Ron.  Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms.  Theoretical Computer Science (TCS), 381(1-3):183–196, 2007.
  * [PS16] David Peleg and Shay Solomon.  Dynamic $(1+\epsilon)$-approximate matchings: a density-sensitive approach.  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 712–729, 2016.
  * [PS18] Ami Paz and Gregory Schwartzman.  A $(2+\epsilon)$-approximation for maximum weight matching in the semi-streaming model.  ACM Transactions on Algorithms (TALG), 15(2):18, 2018.
  * [RSW22] Mohammad Roghani, Amin Saberi, and David Wajc.  Beating the folklore algorithm for dynamic matching.  In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS), pages 111:1–111:23, 2022.
  * [San07] Piotr Sankowski.  Faster dynamic matchings and vertex connectivity.  In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 118–126, 2007.
  * [Sol16] Shay Solomon.  Fully dynamic maximal matching in constant update time.  In Proceedings of the 57th Symposium on Foundations of Computer Science (FOCS), pages 325–334, 2016.
  * [Viz64] Vadim G Vizing.  On an estimate of the chromatic class of a p-graph.  Diskret analiz, 3:25–30, 1964.
  * [Waj20] David Wajc.  Rounding dynamic matchings against an adaptive adversary.  In Proceedings of the 52nd Annual ACM Symposium on Theory of Computing (STOC), pages 194–207, 2020.
  * [YYI12] Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito.  Improved constant-time approximation algorithms for maximum matchings and other optimization problems.  SIAM Journal on Computing (SICOMP), 41(4):1074–1093, 2012.