Streaming Maximal Matching with Bounded Deletions

We start by motivating and explaining the main ideas underlying our main algorithmic result, namely, Theorem 1. We start by observing that in absence of any deletions, one can simply store a maximal matching to solve the problem. On the other hand, when deletions are unbounded, we can simply store $\tilde{\mathrm{\Theta }}(n^2)$ ${\mathrm{\ell }}_0$-samplers to solve the problem by recreating the surviving graph. Our algorithmic approach below is based on a new data structure, called hierarchical maximal matching, which in conjunction with a hierarchical approach for storing ${\mathrm{\ell }}_0$-samplers, allows us to design an algorithm whose space complexity smoothly interpolates between these two extremes.

Let $I$ denote the edges inserted during the stream, and let $D$ denote the edges deleted in the stream. Observe that $I$ and $D$ may be multisets since an edge can be inserted, subsequently deleted, and then reinserted again, and so on. Together, these sets define the graph $G(V,E)$ revealed by the dynamic stream where $E=I\setminus D$.

Our algorithm has two phases where in the first phase, we build a hierarchical collection of maximal matchings using only edges in $I$ along with a data structure $𝐃$ for matching repair to account for deletions. In the second phase, we recover a maximal matching by starting with the least damaged maximal matching in our hierarchical collection, and repairing it using the edges stored in the data structure $𝐃$. We now explain this approach in more detail.

Suppose that we create a sequence of hierarchical maximal matchings, say, $M_1,M_2,\mathrm{\dots },M_L$, using only the edges inserted in the stream (that is, the multiset $I$), ignoring all deletions. Specifically, we start by initializing $M_1,M_2,\mathrm{\dots },M_L$ to be $\mathrm{\varnothing }$. Now, whenever an edge, say $(x,y)$, is inserted, we first try adding it to matching $M_1$. If one of $x$ or $y$ is already matched, then we try adding this edge $(x,y)$ to $M_2$, and continue in this manner. If we are unsuccessful all the way up to $M_L$, then we simply discard this edge. It is clear that this hierarchical collection can be implemented as a streaming algorithm using only $\tilde{O}(n\cdot L)$ space, since each matching can have only $O(n)$ edges. Now suppose there is an index $\mathrm{\ell }\in [L]$ such that none of the edges in $M_{\mathrm{\ell }}$ are deleted, that is, $M_{\mathrm{\ell }}\cap D=\mathrm{\varnothing }$. Then we can recover a maximal matching $M$ in the graph $G(V,E)$ as follows. We initialize $M=M_{\mathrm{\ell }}$, and then greedily add edges in $(M_1\cup M_2\cup \mathrm{\dots }{M}_{\mathrm{\ell }-1})\setminus D$ to $M$ so that $M$ is a maximal matching w.r.t. edges in $(M_1\cup M_2\cup \mathrm{\cdots }\cup M_{\mathrm{\ell }})\setminus D$. We now claim that $M$ must be maximal in $G(V,E)$. Suppose not, then there is an edge $(u,v)\in E$, such that neither $u$ nor $v$ are matched in $M$. But then the edge $(u,v)$ must not be present in any of $(M_1\cup M_2\cup \mathrm{\cdots }\cup M_{\mathrm{\ell }})\setminus D$. This means that when the edge $(u,v)$ arrived in the stream, at least one of $u$ or $v$ must have been matched in $M_{\mathrm{\ell }}$. This now is a contradiction to our assumption, $M_{\mathrm{\ell }}\cap D=\mathrm{\varnothing }$, and hence it cannot be that both $u$ and $v$ are unmatched in $M$. Thus $M$ is maximal with respect to $E=I\setminus D$.

Of course, the only way to ensure that there exists some index $\mathrm{\ell }\in [L]$ such that none of the edges in $M_{\mathrm{\ell }}$ are deleted is to set $L=\mathrm{\Omega }(K)$, and doing so immediately yields our deterministic algorithm that uses space $\tilde{O}(n\cdot K)$. To obtain an $\tilde{O}(n\cdot \sqrt{K})$ space algorithm, we instead set $L=\sqrt{K}$, and observe that this ensures that there exists an index $\mathrm{\ell }\in [L]$ such that at most $\sqrt{K}$ edges in $M_{\mathrm{\ell }}$ are deleted. The second phase of the algorithm now starts on the task of repairing $M_{\mathrm{\ell }}$ to be a maximal matching. Suppose an edge $(u,w)$ is deleted from $M_{\mathrm{\ell }}$. We would like to see if the edges in $E\setminus (M_1\cup M_2\cup \mathrm{\dots }{M}_{\mathrm{\ell }})$ can match $u$ and/or $w$ again. Let us focus on vertex $u$. Our data structure $𝐃$ will store $\mathrm{\Theta }({\log }^{3}n)$ ${\mathrm{\ell }}_0$-samplers for each vertex $x\in V$, with each sampler sampling uniformly at random from the incident edges on $x$. We open these ${\mathrm{\ell }}_0$-samplers for $u$, and if we find an edge $(u,v)$ such that the vertex $v$ is unmatched, we add it to $M_{\mathrm{\ell }}$. Otherwise, there are two possibilities: (a) the degree of $u$ is $O({\log }^{2}n)$ and we have recovered all incident edges on $u$, or (b) the degree of $u$ is $\mathrm{\Omega }({\log }^{2}n)$, and we recover at least $\mathrm{\Omega }({\log }^{2}n)$ distinct neighbors of $u$, all of whom are matched in $M_{\mathrm{\ell }}$. In case (a), we are immediately in good shape because we have recovered all edges incident on $u$, and we can use them to match $u$ at the end if one of the neighbors of vertex $u$ remains unmatched. The more interesting situation is case (b) where on the one hand, the recovered information is not sufficient to repair $u$. On the other hand, we cannot rule out the possibility that $u$ could have been matched, if only we had allocated more space in $𝐃$ to recover additional edges incident on $u$. We next describe how we eliminate this uncertainty.

We create a collection $V_1,V_2,\mathrm{\dots },V_R$ of subsets of $V$ where the set $V_i$ is a random subset of $V$ of size $n/{\log }^{i}n$, and $R=\mathrm{\Theta }(\log n/\log \log n)$. For each vertex $w\in V_i$, our data structure $𝐃$ stores $\mathrm{\Theta }({\log }^{i+3}n)$ ${\mathrm{\ell }}_0$-samplers. It is worth noting that while we are storing more and more ${\mathrm{\ell }}_0$-samplers per vertex as $i$ increases, the total space used by vertices in $V_i$ remains $\tilde{O}(n)$ as the size of $V_i$ shrinks proportionately. We now return to repairing vertex $u$ that ended in case (b) above: we recovered a set $N(u)$ of $\mathrm{\Omega }({\log }^{2}n)$ neighbors of $u$, such that each vertex in $N(u)$ is currently matched. Since every vertex is contained in $V_1$ with probability $1/\log n$, it follows that, with high probability, there must be a vertex $v_1\in N(u)$ such that $v_1$’s mate in $M_{\mathrm{\ell }}$, say $u_1$, belongs to $V_1$. We now add the edge $(u,v_1)$ to $M_{\mathrm{\ell }}$, thereby matching vertex $u$, but now creating a new unmatched vertex, namely, $u_1$. It may seem as if we have not made any progress and the vertices $u$ and $u_1$ have simply traded places. But in fact we have made some progress. Since $u_1\in V_1$, compared to vertex $u$, our data structure $𝐃$ stores $\mathrm{\Theta }(\log n)$ times more information about edges incident on $u_1$, better positioning us to find a mate for $u_1$. We now repeat the above process for vertex $u_1$, either successfully matching it to an unmatched vertex, or recovering all incident edges on $u_1$, or finding a matched vertex $v_2\in N(u_1)$ such that $v_2$’s mate in $M_{\mathrm{\ell }}$, say $u_2$, belongs to $V_2$. The repair successfully terminates if either of the first two events occurs. Otherwise, we now add the edge $(u_1,v_2)$ to $M_{\mathrm{\ell }}$, thereby matching vertex $u_1$, but now creating a new unmatched vertex in $M_{\mathrm{\ell }}$, namely, $u_2$. We then continue this process from $u_2$. The repair process is guaranteed to successfully terminate when we reach $V_R$ since for each vertex in the final set $V_R$, our data structure $𝐃$ stores $\mathrm{\Theta }(n\log n)$ ${\mathrm{\ell }}_0$-samplers each, enough to recover their entire neighborhoods.

To summarize, using $\tilde{O}(n)$ space, the data structure $𝐃$ provides a mechanism to repair an unmatched vertex $u$ in $M_{\mathrm{\ell }}$ due to edge deletions. Since $M_{\mathrm{\ell }}$ can have up to $\sqrt{K}$ edge deletions, to repair all of them, the data structure $𝐃$ independently replicates the above strategy $O(\sqrt{K})$ times to repair all deletions in $M_{\mathrm{\ell }}$. The overall space used by the algorithm is thus $\tilde{O}(n\cdot \sqrt{K})$ for storing the edges in the hierarchical matching, and another $\tilde{O}(n\cdot \sqrt{K})$ space for the repair data structure $𝐃$, giving us the desired space bound of $\tilde{O}(n\cdot \sqrt{K})$.

Finally, it is worth underlining that the computations of the hierarchical matching and the matching repair data structures are independent. Furthermore, the matching repair data structure is computed by a linear sketching algorithm, as it is usual in the insertion-deletion setting, and the hierarchical matching data structure is computed by a (non-linear) deterministic sketch, i.e., a Greedy algorithm, as is it typical in the insertion-only setting.

We now explain the ideas behind our main lower bound result, established in Theorem 2. Our lower bound is best understood as an extension of the tight $\mathrm{\Omega }(n^2/{\alpha }^3)$ space lower bound by Dark and Konrad [14] for one-pass insertion-deletion streaming algorithms that compute an $\alpha$-approximation to Maximum Matching¹¹1[6] gives an algorithm that achieves this space bound up to constant factors, see also [21, 4, 10].. We will denote this lower bound as the DK20 lower bound in the following. Due to the well-known fact that any maximal matching is at least half the size of a largest matching, DK20 immediately yields an $\mathrm{\Omega }(n^2)$ space lower bound for Maximal Matching.

In the following, we will treat the DK20 lower bound as if it was established for Maximal Matching. DK20 is proved in the one-way two-party communication setting. In this setting, the first party, denoted Alice, holds the edge set $E$ of a bipartite graph $G=(A,B,E)$, and the second party, denoted Bob, holds edge deletions $D\subseteq E$. Alice sends a message to Bob, and, upon receipt, Bob is required to output a maximal matching in the graph $G^{\prime }=(A,B,E\setminus D)$, i.e., Alice’s input graph with Bob’s deletions applied. Since Alice and Bob can simulate the execution of an insertion-deletion streaming algorithm for Maximal Matching on their input, by forwarding the memory state of the algorithm from Alice to Bob in form of a message, a lower bound on the size of the message used in the communication setting therefore also constitutes a lower bound on the memory required by such algorithms.

In DK20, Alice holds a bipartite random graph $G=(A,B,E)$ with $|A|=|B|=n$ so that every edge is inserted into the graph with probability $\frac{1}{2}$. Bob holds subsets $A^{\prime }\subseteq A$ and $B^{\prime }\subseteq B$, with $|A^{\prime }|=|B^{\prime }|=\frac{4}{5}n$, and inserts deletions into the vertex-induced subgraph $G[A^{\prime }\cup B^{\prime }]$ such that, after the deletions are applied, the remaining edges in $G[A^{\prime }\cup B^{\prime }]$ form a large matching $M$. It is proved that recovering a constant fraction of the edges of $M$ – a task that a protocol for Maximal Matching necessarily must achieve – requires space $\mathrm{\Omega }(n^2)$. On a technical level, DK20 give a sophisticated reduction to the well-known one-way two-party Augmented-Index communication problem. In Augmented-Index, Alice holds a bitstring $X\in {\{0,1\}}^n$, and Bob holds a index $J\in [n]$ as well as the suffix $X[J+1,n]$. Alice sends a message to Bob who is tasked with reporting the bit $X[J]$. It is well-known that solving Augmented-Index with probability bounded away from $\frac{1}{2}$ requires a message of size $\mathrm{\Omega }(n)$. In DK20, the reduction is such that the bits $X$ of an Augmented-Index instance correspond to edges in the random graph with the property that, with constant probability, the bit $X[J]$ corresponds to an edge in the matching $M$. This construction is such that the mapping between $X[J]$ and the edges in $M$ is random and, most importantly, unknown to the underlying protocol. Hence, a protocol that reports a constant fraction of the edges of $M$ will therefore report the edge that corresponds to bit $X[J]$ with constant probability, which then solves Augmented-Index.

Bob holds $\mathrm{\Theta }(n^2)$ deletions in the DK20 construction. In order to decrease the number of deletions to $K$, we proceed as follows. In our lower bound construction, Alice holds a graph $G=G_1\dot{\cup }{G}_2\dot{\cup }\mathrm{\dots }\dot{\cup }{G}_s$, which is a vertex-disjoint union of $s$ graphs ${(G_i)}_{1\le i\le s}$. Each graph $G_i$ has $\sqrt{K}$ vertices and constitutes a scaled-down version of Alice’s input graph in the DK20 construction, namely a bipartite random graph with edge probability $\frac{1}{2}$. Bob holds an index $I\in \{1,\mathrm{\dots },s\}$, which identifies one of the graphs $G_I$. Furthermore, Bob holds the counterpart to Bob’s input in the DK20 construction to graph $G_I$, i.e., edge deletions that apply to $G_I$. Bob leaves all the other graphs $G_j$, with $j\ne I$, untouched.

We establish a direct sum argument to show that this problem requires a large message size. The key insight is that, since Alice does not know the index $I$, the message sent from Alice to Bob must contain sufficient information so that Bob can output a maximal matching no matter from which graph $G_i$ Bob has deleted some edges. In other words, Alice and Bob must be able to solve $s$ independent copies of the DK20 lower bound instance. Since each graph $G_i$ has $\sqrt{K}$ vertices, DK20 implies that $\mathrm{\Omega }(K)$ bits are required for solving one copy. Hence, overall, space $\mathrm{\Omega }(K\cdot s)$ is required. Last, to make sure that the final graph has $n$ vertices, we need to set $s=\mathrm{\Theta }(\frac{n}{\sqrt{K}})$, which delivers the claimed $\mathrm{\Omega }(n\cdot \sqrt{K})$ space lower bound.

To implement this approach, we first define a generalization of Augmented-Index denoted Embedded-Augmented-Index, where Alice holds $s$ binary strings $X_1,\mathrm{\dots },X_s\in {\{0,1\}}^t$, Bob holds two indices $I\in [s]$ and $J\in [t]$ as well as the suffix $X_I[J+1,t]$, and the objective for Bob is to output the bit $X_I[J]$. Using by now standard information-theoretic arguments, we show that this problem requires $\mathrm{\Omega }(t\cdot s)$ bits of communication. Next, following the proof outline of DK20, we show that a bounded-deletion streaming algorithm can be used to solve Embedded-Augmented-Index, which completes the proof.

Our lower bound for deterministic algorithms works with a family of bipartite graphs $G=(A,B,E)$ that have the property that, even when any $K$ edges $D\subseteq E$ are deleted from $G$, then still every maximal matching in $G-D$ matches all $A$-vertices. The family of graphs ${𝒢}_K(n)$ is obtained as follows. Given the deletion budget $K$, define ${\mathscr{H}}_K$ to be the family of bipartite graphs $H=(A,B,E)$ with $|A|=K,|B|=3K$, and the degree of every $A$-vertex is $2K$. Then, ${𝒢}_K(n)$ is the family of graphs consisting of the disjoint union of any $n/(4K)$ graphs from ${\mathscr{H}}_K$.

Similar to our lower bound for randomized algorithms, we prove our lower bound in the one-way two-party communication setting. Alice holds a graph $G\in {𝒢}_K(n)$ as input, and Bob holds up to $K$ edge deletions $D\subseteq E(G)$. We now claim that a protocol $\pi$ for Maximal Matching that outputs a maximal matching in the graph $G-D$ allows Bob to learn $K+1$ incident edges on every $A$-vertex. Once this claim is established, we finalize the proof by observing that, if the message from Alice to Bob was of size $o(n\cdot K)$, then $\pi$ also constitutes an encoding of these overall $\frac{n(K+1)}{4}$ edges‘using only $o(n\cdot K)$ bits. This in turn can be used to encode the graph class ${𝒢}_K(n)$ with fewer bits than dictated by the information-theoretic threshold - a contradiction.

To see that Bob can learn $K+1$ edges incident on every $A$-vertex in input graph $G\in {𝒢}_K(n)$, Bob proceeds as follows. Let $a\in A$ be any vertex and $\pi$ the message received from Alice. Bob then completes the protocol without introducing any deletions, recovering a maximal matching $M_1$ that, as discussed above, necessarily matches the vertex $a$. Let $e_1$ be the edge incident on $a$ in $M$. Next, Bob completes another run of the protocol starting with message $\pi$ and feeding the edge $e_1$ as edge deletion into the protocol. In doing so, Bob obtains another maximal matching $M_2$ that necessarily matches $a$, thereby recovering a second edge $e_2$ incident on $a$. Repeating this process, Bob learns more and more edges incident on $a$, feeding these edges as deletions into the protocol in the next simulation. Overall, Bob can repeat this process $K$ times, thereby exhausting the deletion budget, which allows him to learn $K+1$ edges incident on $a$. Finally, this process can be repeated for every $a\in A$, which completes the argument.

We now briefly describe the main idea behind the algorithmic result stated in Theorem 4. Once again, similar to Theorem 1, our algorithm utilizes the hierarchical matching data structure, but with some crucial modifications.

Specifically, this time we implement a budgeted version of the hierarchical matching data structure on the insertions part of the stream, where instead of having a fixed number of levels, we now have an overall budget $B$ on the total number of edges stored in the hierarchical matching data structure. The data structure maintains a lexicographic maximality property whereby an edge insertion that may cause the number of stored edges to exceed the budget $B$ triggers removal of an edge from the current last level of the data structure. The number of levels in the data structure forms a bitonic sequence over time, in that, it may keep increasing as long as the space budget $B$ has not been reached, but once that happens, the number of levels steadily decreases as enforcing the lexicographic property can trigger many deletions from the last levels of the hierarchical matching as the remainder of the insertion stream is processed.

An immediate consequence of this lexicographic property is that if upon termination, we have a sequence of hierarchical matchings, say, $M_1,M_2,\mathrm{\dots },M_L$, then $M_1,M_2,\mathrm{\dots },M_{L-1}$ must necessarily constitute a $(L-1)$-level hierarchical maximal matching data structure. We also separately store all deletions that appear in the stream. Now by setting our budget $B$ to be $\tilde{\mathrm{\Theta }}(n+K)$, we can show that when we apply deletions, one of the $(L-1)$ maximal matchings, say $M_i$, necessarily loses at most an $o(1)$-fraction of its edges. We can then extend $M_i$ to be an “almost” maximal matching $M$ in the overall stream, by greedily inserting surviving edges in $M_1,M_2,\mathrm{\dots },M_{i-1}$ into it. Here the “almost” refers to the fact that unlike the maximal matching algorithm of Theorem 1, we do not need to repair the missing $o(1)$-fraction edges in $M_i$ to ensure maximality. The final matching $M$ is easily shown to be a $(2+o(1))$-approximate matching, giving us the desired result.

We prove this lemma by contradiction. To this end, assume that there exists an edge $(u,v)\in E\setminus M$ such that $M\cup \{(u,v)\}$ is a matching.

We first argue by contradiction that $V(M_{\mathrm{\ell }})\cap \{u,v\}=\mathrm{\varnothing }$. Indeed, suppose that this was not the case and, w.l.o.g., assume that $u\in V(M_{\mathrm{\ell }})$. By the statement of the lemma, then either $u$ is matched in $M$ or the entire neighborhood of $u$ is known, i.e., $N(u)\subseteq F$, which implies that $(u,v)\in F$. In the first case, we immediately arrive at a contradiction since the edge $(u,v)$ could not be added to $M$ since $u$ is already matched. In the second case, observe that we attempted to greedily add the edges of $F$ to $M$, in particular, we already attempted to add the edge $(u,v)$ to $M$, which also yields a contradiction.

Assume therefore that $V(M_{\mathrm{\ell }})\cap \{u,v\}=\mathrm{\varnothing }$. This, however, implies that, when the edge $(u,v)$ arrived in the stream, it was not included in $M_{\mathrm{\ell }}$ despite both endpoints being free in $M_{\mathrm{\ell }}$. Suppose the edge $(u,v)$ occurs $\beta$ times in the stream $I$. It must then be the case that all $\beta$ copies of this edge in $I$ must have been added to one or more of the matchings $M_1,\mathrm{\dots },M_{\mathrm{\ell }-1}$. On the other hand, since edge $(u,v)\in E\setminus M$, it means that the numbers of times $(u,v)$ is deleted in $D$ is strictly less than $\beta$. So at least one copy of the edge $(u,v)$ in $M_1,\mathrm{\dots },M_{\mathrm{\ell }-1}$ remains undeleted, after we remove edges in $D$. Since we attempted to add the surviving edges of $M_1,\mathrm{\dots },M_{\mathrm{\ell }-1}$ to $M$, we also arrive at a contradiction.

It follows then that the matching $M$ is indeed maximal in $G$. $◀$

The second key ingredient of our analysis is a progress lemma that shows that the fixing process yields the desired result. In more detail, we show that, in iteration $i$ of the loop in Line 17, when fixing any vertex $u_j\in (V(M_{\mathrm{\ell }})\cap V_i)$ that is currently unmatched but was matched in $M_{\mathrm{\ell }}$, then we either (i) recover all of $u_j$’s neighbors, (ii) we are able to match $u_j$ directly to a yet unmatched vertex, or (iii) we can match $u_j$ to an already matched vertex $v$ such that $v$’s mate $u^{\prime }$ in the current matching is contained in level $i+1$, i.e., $u^{\prime }\in V_{i+1}$.

We first recall that $N_{i,j}(u)$ consists of ${\log }^{i+3}(n)$ ${\mathrm{\ell }}_0$-samplers.

Suppose that Items 1 and 2 are false. Since Item 1 is false, the degree of $u$ cannot be too small since otherwise the ${\mathrm{\ell }}_0$-samplers would have picked up every single edge incident to $u$. We prove in Lemma 8 that, w.h.p., the degree of $u$ is at least ${\log }^{i+2}(n)/C^{\prime }$. Then, since Item 2 is false, all vertices produced by the ${\mathrm{\ell }}_0$-samplers in $N_{i,j}(u)$ are matched in $M$. Denote by $U$ their mates in $M$. Then, $|U|\ge {\log }^{i+2}(n)/C^{\prime }$. Then, the probability that none of the vertices in $U$ are contained in $V_{i+1}$ is:

where we used Lemma 9 stated in the appendix, then used the inequality $1+x\le \exp (x)$, and then assumed that $C$ and $C^{\prime }$ are picked such that $\frac{C}{C^{\prime }}$ is large enough. Hence, such a vertex exists with high probability, which completes the proof. $◀$

First, observe that $N_{i,j}(v)$ consists of ${\log }^{i+3}(n)$ ${\mathrm{\ell }}_0$-samplers for each vertex $v\in V_i$. Let $u\in N(v)$ be a vertex. Then, assuming that none of the ${\mathrm{\ell }}_0$-samplers fail, the probability that the outcome of an ${\mathrm{\ell }}_0$-sampler for $v$ is $u$ is at least $\frac{1}{\mathrm{deg}(v)}\ge \frac{C^{\prime }}{{\log }^{i+2}(n)}$. Since all samplers operate independently, the probability that none of the samplers produce $u$ is at most:

using the inequality $1+x\le \exp (x)$ and by picking a sufficiently large value for $C^{\prime }$. By a union bound over the vertices in $N(v)$, we obtain that all vertices in $N(v)$ are contained in the ${\mathrm{\ell }}_0$-samplers with high probability. Last, by a union bound over all values of $j$, the result follows. $◀$

We observe that the previous lemma implies the important property that, for every vertex $v\in V_R$ with $R=\frac{\log (n)+\log (C^{\prime })}{\log \log n}-2$ as in the algorithm, i.e., a vertex contained in the last level $R$, the entire neighborhood of $v$ is contained in $N_{R,j}(v)$ since ${\log }^{R+2}(n)/C^{\prime }\ge n.$

We are now ready to prove our main result, i.e., Theorem 1.

We first address the space complexity and then establish correctness.

The algorithm stores the $\sqrt{K}$ matchings $M_1,\mathrm{\dots },M_{\sqrt{K}}$, which requires space $\tilde{O}(n\sqrt{K})$. In addition, the algorithm stores various ${\mathrm{\ell }}_0$-samplers. The number of these samplers is bounded by

and, since each ${\mathrm{\ell }}_0$-sampler uses space $\tilde{O}(1)$, the space bound follows.

To establish correctness, we will argue that after the loop in Line 12, which ends in Line 27, but before Line 28 is executed, the matching $M$ together with the set of ${\mathrm{\ell }}_0$-samplers fulfill the premises of Lemma 6. Invoking the lemma then establishes that executing Line 28 turns $M$ into a globally maximal matching, which completes the proof.

To argue that $M$ fulfills the premises of Lemma 6 after Line 27 (but before Line 28), we need to ensure that, for every vertex $u\in V(M_{\mathrm{\ell }})$, either $u$ is matched in $M$ or the entire neighborhood of $u$ is contained in our set of ${\mathrm{\ell }}_0$-samplers. In the following, we say that a vertex $u\in V(M_{\mathrm{\ell }})$ fulfills property $P$ if it is either matched in $M$ or its entire neighborhood is contained in our ${\mathrm{\ell }}_0$-samplers.

Observe that when entering the loop in Line 12, the vertices $V(M_{\mathrm{\ell }}\setminus M_{\mathrm{\ell }}^{\prime })$ are exactly those vertices that violate property $P$. We will now argue that each iteration of this for-loop fixes one of these vertices and, in particular, it does not introduce any new vertices that may violate this property. This then completes the proof.

Consider thus the iteration $j$ that fixes vertex $u_j$. First, it may happen that $u_j$ was matched when fixing a vertex $u_{j^{\prime }}$, for some . This is checked in Line 13, and if this happens then we are done. Otherwise, we enter the loop in Line 17. The vertex $u$ is initialized as the vertex $u_j$ that we attempt to fix. The loop satisfies the invariant that, in iteration $i$, we are guaranteed that $u\in V_i$. This is clearly the case for the first iteration $i=0$ since $V_0=V$. To see that this holds throughout, we will argue that an iteration of the loop always establishes property $P$ for the current vertex $u$. Fixing vertex $u$ may however come at the cost of introducing a new violation of property $P$ for a previously matched vertex $u^{\prime }$. This vertex $u^{\prime }$, however, is then necessarily contained in the vertex set $V_{i+1}$. Since at the end of the loop, we set $u\leftarrow u^{\prime }$, we therefore see that in the subsequent iteration $i+1$, the vertex $u$ is now contained in $V_{i+1}$, as desired.

Now, to see that $u$ is always fixed, we invoke our progress lemma, Lemma 7, which states that either the entire neighborhood of $u$ is contained in our ${\mathrm{\ell }}_0$-samplers (case 1) or $u$ is rematched (cases 2 and 3), which implies that $u$ now satisfies property $P$. Case 3 matches $u$ to a previously matched vertex $v$ whose mate $u^{\prime }$ becomes unmatched. However, as proved in Lemma 7, $u^{\prime }$ is then necessarily contained in $V_{i+1}$.

Last, to see that in the final iteration of the loop in Line 17, no new vertex that violates property $P$ is introduced, we observe that the last level $V_R$ is such that the entire neighborhood of every vertex in $V_R$ is stored in the ${\mathrm{\ell }}_0$-samplers $N_{R,j}(u)$, for every $j$, which is a consequence of Lemma 8.

Thus, overall, we have established that each iteration of the main for loop fixes a vertex and does not introduce any new vertices that violate property $P$. Lemma 6 thus establishes that Line 28 turns $M$ into a globally maximal matching, which establishes that the output matching is maximal and completes the proof. $◀$

We will give a reduction to ${\text{Embedded-Augmented-Index}}_{s,t}$. For integers $s,t$ whose values we will determine later, let $X=X_1,\mathrm{\dots },X_s\in {\{0,1\}}^t,I\in [s]$, and $J\in [t]$ be an ${\text{Embedded-Augmented-Index}}_{s,t}$ instance, and let $𝒜$ be a bounded-deletion streaming algorithm for Maximal Matching that outputs a maximal matching with probability $\frac{2}{3}$ on every instance. We assume that, if $𝒜$ fails, then it still outputs a matching, but it may not be maximal.

Given $X$, Alice constructs the bipartite graph $G=G_1\dot{\cup }{G}_2\dot{\cup }\mathrm{\dots }\dot{\cup }{G}_s$, which is the disjoint union of the graphs ${(G_i)}_{1\le i\le s}$. We now describe the construction of graph $G_i$, for any $1\le i\le s$. The vertex set $A_i\cup B_i$ of $G_i$ is such that $|A_i|=|B_i|=10\cdot \sqrt{t}$. The edge set $E_i$ of $G_i$ is best described via its bipartite incidence matrix $M_i$. To obtain $M_i$, we first construct the matrix ${\tilde{M}}_i$, which has the same dimensions as $M_i$. The construction process is as follows:

1. 1.

   The top-left square sub-matrix of ${\tilde{M}}_i$ with side length $\sqrt{t}$ is filled with the entries of $X_i$ from left-to-right and top-to-bottom.

2. 2.

   All other entries of ${\tilde{M}}_i$ are filled with uniform random bits obtained via public randomness.

3. 3.

   Alice and Bob sample a random binary square matrix $Y_i$ with side length $10\sqrt{t}$ such that each entry is $1$ with probability $\frac{1}{2}$. They compute the entry-wise XOR between ${\tilde{M}}_i$ and $Y_i$. Let ${\tilde{M}}_i^{\prime }$ denote the resulting matrix.

4. 4.

   Alice and Bob sample random permutations ${\sigma }_i,{\pi }_i:[10\sqrt{t}]\to [10\sqrt{t}]$ from public randomness. The matrix $M_i$ is obtained from ${\tilde{M}}_i^{\prime }$ by permuting the rows and columns with the permutations ${\sigma }_i$ and ${\pi }_i$, respectively.

Alice then runs algorithm $𝒜$ on the edges of $G$, presented to $𝒜$ in random order.

Recall that Bob holds the indices $I\in [s]$ and $J\in [t]$ as well as the suffix $X_I[J+1,\mathrm{\dots },t]$. Bob introduces edge deletions, but only into the graph $G_I$. To this end, consider the matrix ${\tilde{M}}_I$, and let $a,b$ be such that the entry ${\tilde{M}}_I[a,b]$ corresponds to the bit $X_I[J]$. Then, observe that Bob knows all entries of the submatrix ${\tilde{M}}_I^{\prime }(a,b)$ with top-left corner at position $(a,b)$ and bottom-right corner being the bottom-right corner of ${\tilde{M}}_I^{\prime }$ except the top-left entry ${\tilde{M}}_I^{\prime }(a,b)[a,b]$, either because the bits $X_I[J+1,t]$ (XORed with entries of $Y_I$) correspond to these entries or the entries were constructed entirely from public randomness. Denote by

the entries of ${\tilde{M}}_I^{\prime }$ that constitute off-diagonal entries in the submatrix ${\tilde{M}}_I^{\prime }(a,b)$. Then, for each index $(i,j)\in ℐ$, if $M_I[\sigma (i),\pi (j)]=1$ then Bob feeds an edge deletion that turns this entry to $0$ into the algorithm $𝒜$, i.e., $M_I[\sigma (i),\pi (j)]=0$ after the deletion. All deletions are fed into $𝒜$ in random order.

Bob then obtains the output matching $OUT$ produced by algorithm $𝒜$.

We denote by $OU{T}_i\subseteq OUT$ the subset of edges that are contained in graph $G_i$.

We assume from now on that the algorithm $𝒜$ does not fail. Then, we claim that, with high probability, $|OU{T}_I|\ge \frac{1}{4}\cdot 9\sqrt{t}-o(\sqrt{t})$. Indeed, observe that none of the diagonal entries in ${\tilde{M}}_I^{\prime }(a,b)$ are subsequently deleted, and the edges corresponding to the $1$-entries of this diagonal form a matching. Observe that both dimensions of ${\tilde{M}}_I^{\prime }(a,b)$ are at least $9\sqrt{t}$. By concentration bounds, with high probability, there are at least $\frac{1}{2}\cdot 9\sqrt{t}-o(\sqrt{t})$ $1$-entries. The claim then follows from the observation that $M_I$ is obtained from ${\tilde{M}}_I^{\prime }$ by permuting the rows and columns, which are operations that preserve the matching size, and by the fact that a maximal matching is at least half the size of a maximum matching.

Hence, with probability $2/3-o(1)$, the algorithm $𝒜$ succeeds and $|OU{T}_I|\ge \frac{1}{4}\cdot 9\sqrt{t}-o(\sqrt{t})$ holds. We assume that these events hold from now on.

We say that the entry $X_I[J]$ materializes as an edge in graph $G_I$ if ${\tilde{M}}_I^{\prime }[a,b]=1$. Recall that ${\tilde{M}}_I^{\prime }[a,b]={\tilde{M}}_I[a,b]XOR{Y}_I[a,b]$, where $Y_I[a,b]$ is a uniform random bit. Hence, $X_I[J]$ materializes as an edge with probability $1/2$.

We will now argue that, if the edge corresponding to $X_I[J]$ materializes, then it is also contained in $OU{T}_I$ with constant probability. Indeed, due to the symmetry of the construction that is achieved by the applications of the random permutations ${\sigma }_i$ and ${\pi }_i$ and the XOR computations with $Y_I$, each of the diagonal entries of ${\tilde{M}}_I^{\prime }(a,b)$ with value $1$ are reported in the matching $OU{T}_I$ with equal probability. Hence, conditioned on the entry $X_I[J]$ materializing as an edge in $G_I$, the algorithm $𝒜$ succeeding, and the event $|OU{T}_I|\ge \frac{9}{4}\sqrt{t}-o(t)$, this edge is contained in $OU{T}_I$ with probability at least

since $OU{T}_I$ contains at least $|OU{T}_I|-2\sqrt{t}$ diagonal entries from the matrix ${\tilde{M}}_I^{\prime }(a,b)$, and any matching in $G_I$ is of size at most $10\sqrt{t}$.

Hence, the probability that the edge corresponding to $X_I[J]$ materializes and is reported in $OU{T}_I$ is at least $\frac{1}{80}-o(1)$ conditioned on $𝒜$ succeeding and on the event $|OU{T}_I|\ge \frac{9}{4}\sqrt{t}-o(t)$. If the edge is not observed in $OU{T}_I$ then the algorithm reports either $0$ or $1$ as a guess for $X_I[J]$, each with probability $\frac{1}{2}$.

Using the following definition of $p$:

we can bound the overall success probability of this strategy as follows:

By Theorem 9, $𝒜$ therefore requires space $\mathrm{\Omega }(s\cdot t)$. Lastly, to ensure that at most $K$ deletions are introduced, we set $t=K$, and to ensure that the input graph has $n$ vertices, we set $s=\frac{n}{2\cdot 10\sqrt{t}}$. The lower bound thus gives $\mathrm{\Omega }(s\cdot t)=\mathrm{\Omega }(\frac{n}{\sqrt{K}}\cdot K)=\mathrm{\Omega }(n\cdot \sqrt{K})$, as desired. $◀$