Faster Semi-Streaming Matchings via Alternating Trees

The main technical claim of our work can be summarized as follows.

The very high-level idea behind our approach is finding “short” augmentations until only a few of them remain. It is folklore that such an algorithm yields the desired approximation. To find these “short” augmentations, each free vertex maintains some set of alternating paths originating at it; we refer to such a set of alternating paths by a structure. The main conceptual contribution of our work is representing these structures by alternating trees and blossoms, introduced by Edmonds in his celebrated work [39]. An alternating tree is a tree rooted at a free vertex such that every root-to-leaf path is an alternating path. A formal, recursive definition of blossoms is given in Definition 5. Informally, a blossom can be either an odd alternating cycle (that is, an odd cycle in which each vertex except one is matched to one of its neighbors in the cycle), or a set of smaller vertex-disjoint blossoms connected by an odd alternating cycle. Our algorithm represents each structure by an alternating tree in which each node can be either a vertex (of the input graph) or a blossom contracted into a single vertex. The most related work to ours, i.e., [48], develops an ad-hoc structure. Although another related work [61] builds on blossom structure, it does it for reasons other than finding short augmentations; in fact, for finding short augmentations [61] uses [48] essentially in a black-box manner. A more detailed overview of prior work is given in Tables 1 and 2.

Our approach provides several advantages: (1) we re-use some of the well-established properties of blossoms; (2) our proof of correctness and our algorithm are simpler compared to that of [48]; (3) we exhibit relations between different alternating trees during the short-augmentation search that eventually lead to our improved pass complexity, from $1/{ϵ}^{19}$ to $1/{ϵ}^6$; and (4) the size of structures in our algorithm is considerably smaller than the structure size in [48]’s algorithm, which leads to the improvement of space complexity from $O(n/{ϵ}^{22})$ to $O(n/{ϵ}^6)$. We hope that this perspective and simplification in the analysis will lead to further improvements in designing approximate maximum matching algorithms.

Our algorithmic setup is inspired by [48] and its predecessor [40], while several structural properties are borrowed from [39]. We detail similarities and differences between our and [48]’s techniques in Section 3.4.

Approximate maximum matchings in (semi-)streaming have been extensively studied from numerous perspectives. The closest to our work is [48], who design a deterministic semi-streaming algorithm for $ϵ\text{MM}$ using $O(1/{ϵ}^{19})$ passes. Prior to that work, [71, 73] developed semi-streaming algorithms that use $\exp (1/ϵ)$ many passes. Tables 1 and 2 list many other results for computing $ϵ\text{MM}$ in semi-streaming; in bipartite and general graphs, respectively.

Next, we briefly describe some related works on variants of the $ϵ\text{MM}$ problem or the underlying model of computation, that have been considered in the literature. A sequence of papers has studied the question of estimating the size of the maximum matching [64, 32, 13, 43, 65]. The $ϵ\text{MM}$ problem has been considered in weighted graphs as well [2, 3, 32, 4, 49, 61, 6]. On bipartite graphs and in the semi-streaming model, any algorithm for (unweighted) $ϵ\text{MM}$ can be converted to an algorithm for weighted $ϵ\text{MM}$ with slightly increased pass and space complexities [27, 26]. Using this conversion, all pass-complexity results in Table 1 also apply to the weighted case, except that the $\log n$ factors are increased to $\log (n/ϵ)$. Considering variants of the streaming setting, there have been works in dynamic streaming where one can both insert and remove edges [67, 32, 35, 14], in the vertex arrival model [66, 55, 62, 42, 34, 31, 50], and in random streaming where vertices or edges arrive in a random order [70, 68, 49, 45, 25, 8].

Several works have studied lower bound questions in the streaming setting, both for exact [57, 17, 33] and approximate maximum matching [55, 62, 14, 13, 15, 63, 5, 18].

The $ϵ\text{MM}$ problem is well-studied in the classical centralized setting as well [37, 38]. Furthermore, in recent years, there has been a growing interest in $ϵ\text{MM}$ in the area of dynamic algorithms [56, 28, 10, 9, 30, 74, 29, 21, 12] and also in sublinear time algorithms for approximate maximum matching [20, 22, 23].

After some preliminaries in Section 2, we give an overview of our approach in Section 3. Next, in Section 4, we present our algorithm from a high level. The complete description and analysis of our algorithm are deferred to the full version [72].

Note that in an alternating tree, every leaf is an outer vertex; every inner vertex $v$ has exactly one child, which is matched to $v$. Hence, every non-root vertex in the tree is matched.

Consider a blossom $B$. A short proof by induction shows that $|B|$ is odd. In addition, $M\cap E_B$ matches all vertices except one. This vertex, which is left unmatched in $M\cap E_B$, is called the base of $B$. Note that $E(B)=E(G)\cap (B\times B)$ may contain many edges outside of $E_B$. Blossoms exhibit the following property.

The following lemma is proven in [39, Theorem 4.13].

Consider a set $\mathrm{\Omega }$ of blossoms. We say $\mathrm{\Omega }$ is laminar if the blossoms in $\mathrm{\Omega }$ form a laminar set family. Assume that $\mathrm{\Omega }$ is laminar. A blossom in $\mathrm{\Omega }$ is called a root blossom if it is not contained in any other blossom in $\mathrm{\Omega }$. Denote by $G/\mathrm{\Omega }$ the undirected simple graph obtained from $G$ by contracting each root blossom of $\mathrm{\Omega }$. For each vertex in ${\bigcup }_{B\in \mathrm{\Omega }}B$, we denote by $\mathrm{\Omega }(v)$ the unique root blossom containing $v$. If $\mathrm{\Omega }$ contains all vertices of $G$, we denote by $M/\mathrm{\Omega }$ the set of edges $\{\{\mathrm{\Omega }(u),\mathrm{\Omega }(v)\}\mid \{u,v\}\in M\text{ and }\mathrm{\Omega }(u)\ne \mathrm{\Omega }(v)\}$ on the graph $G/\mathrm{\Omega }$. It is known that $M/\mathrm{\Omega }$ is a matching of $G/\mathrm{\Omega }$ [38].

In our algorithm, we maintain several vertex-disjoint subgraphs. Each subgraph is associated with a regular set of blossoms, which is a set of blossoms whose contraction would transform the subgraph into an alternating tree satisfying certain properties. A regular set of blossoms is formally defined as follows.

In our algorithm, each undirected edge $\{u,v\}$ is represented by two directed arcs $(u,v)$ and $(v,u)$. Let $(u,v)$ be an arc. We say $(u,v)$ is matched if $\{u,v\}$ is a matched edge; otherwise, $(u,v)$ is unmatched. The vertex $u$ and $v$ are called, respectively, tail and head of $(u,v)$. We denote by $\overleftarrow{(u,v)}=(v,u)$ the reverse of $(u,v)$.

Let $P=(u_1,v_1,\mathrm{\dots },u_k,v_k)$ be an alternating path, where $u_i$ and $v_i$ are vertices, $(u_i,v_i)$ are matched arcs, and $(v_i,u_{i+1})$ are unmatched ones. Let $a_i=(u_i,v_i)$. We often use $(a_1,a_2,\mathrm{\dots },a_k)$ to refer to $P$, i.e., we omit specifying unmatched arcs. Nevertheless, it is guaranteed that the input graph contains the unmatched arcs $(v_i,u_{i+1})$, for each . If $P$ is an alternating path that starts and/or ends with unmatched arcs, e.g., $P=(x,u_1,v_1,\mathrm{\dots },u_k,v_k,y)$ where $(x,u_1)$ and $(v_k,y)$ are unmatched while $a_i=(u_i,v_i)$ for $i=1\mathrm{\dots }k$ are matched arcs, we use $(x,a_1,\mathrm{\dots },a_k,y)$ to refer to $P$. In our case, very frequently, $x$ and $y$ will be free vertices, usually $x=\alpha$ and $y=\beta$.

In the semi-streaming model [46], we assume that the algorithm has no random access to the input graph. The set of edges is represented as a stream. In this stream, each edge is presented exactly once, and each time the stream is read, edges may appear in an arbitrary order. The stream can only be read as a whole and reading the whole stream once is called a pass (over the input). The main computational restriction of the model is that the algorithm can only use $O(n\mathrm{poly}\log n)$ words of space, which is not enough to store the entire graph if the graph is sufficiently dense.

In our algorithm, each free vertex maintains an alternating tree. These trees are created via a DFS exploration in an alternating-path manner. Consider an alternating tree $S$. $S$ is associated with a so-called working vertex, which represents the last vertex the DFS exploration has currently reached. Figure 1 depicts an alternating tree.

Recall that the goal is to look for short augmentations. Hence, these DFS explorations are carried out by attempting to visit an edge by as short an alternating path as possible. In particular, each matched edge $e$ maintains a label $\mathrm{\ell }(e)$ representing the so-far shortest discovered alternating path to a free vertex.¹¹1Our algorithm maintains arc labels; an edge $\{u,v\}$ is represented by arcs $(u,v)$ and $(v,u)$, and the algorithm maintains $\mathrm{\ell }((u,v))$ and $\mathrm{\ell }((v,u))$. For the sake of simplicity, in this overview, we only talk about edge labels. Observe that only matched edges maintain labels. That enables storing those labels in $O(n)$ words.

In a single pass, the working vertex $u$ of $S$ attempts to extend $S$ by a length-$2$ path $\{u,v,t\}$, where $g=\{u,v\}$ is unmatched and $e=\{v,t\}$ is a matched edge; if it is impossible, just like in a typical DFS, this working vertex backtracks. Then, one of the following happens (see the full version for details):

1. 1.

   The edge $g$ connects $S$ with an alternating tree $S^{\prime }$, different than $S$, such that there is an augmenting path between the roots of $S$ and $S^{\prime }$ involving $g$. In that case, this augmenting path is recorded, and $S$ and $S^{\prime }$ are temporarily removed from the graph. This is done by procedure Augment. (After the DFS exploration is completed, the algorithm restores all temporarily removed vertices and augments the matching using the recorded augmenting paths.)

2. 2.

   If $g$ connects two vertices in $S$ such that it creates a blossom, then this blossom is contracted. This is done by procedure Contract. These contractions ensure that the exploration subgraph from each free vertex looks like a tree.

3. 3.

   The alternating path along $S$ to $e$ is shorter than $\mathrm{\ell }(e)$. Then, $g$ and $e$ are added to $S$, and $\mathrm{\ell }(e)$ is updated accordingly. If $e$ belongs to another alternating subtree, which might belong to $S$ or another alternating tree, then the entire subtree together with $e$ is appended to $u$. This is done by procedure Overtake. Note that, by the construction, the last edge appended to DFS exploration is matched. An example of Overtake is depicted in Figure 2.

   $▶$ Remark 13.

   The intuition behind the overtake operation is as follows. In our algorithm, an edge label represents the shortest alternating distance from a free vertex to the edge. Thus, when $S$ finds a shorter path to $e$, Overtake allows $S$ to take over the search on $e$ and reduce its label. This operation helps the algorithm find shorter alternating paths to each matched edge.

The described operations are very natural when we take the perspective of maintaining edge labels and alternating trees. However, why do they yield an approximate maximum matching? Moreover, how many passes does the entire process take?

Recall that our algorithm executes many DFS explorations in parallel, each originating at a free vertex. When a DFS exploration from a free vertex has no new edges to visit, we say that the free vertex becomes inactive; otherwise, it is active. Our algorithm terminates when the number of active free vertices becomes a small fraction of the current matching size. The main goal of our correctness proof is to show that terminating the search for augmentations is justified. Speaking informally, the intuition behind our correctness argument is that if our algorithm runs indefinitely, each short augmentation will eventually intersect an augmentation our algorithm has already found.

Our proof of correctness boils down to showing the following:

Recall that our algorithm maintains augmenting trees from free vertices. On a very high level, this enables us to think about augmentation search as, informally speaking, it is done on bipartite graphs. In particular, we show the following invariant:

At the beginning of every pass, if a non-tree edge induces an odd cycle, that edge cannot be reached by any so far discovered alternating path starting at a free vertex.

One can also view this invariant as a way of saying that no relevant odd cycle is visible to the algorithm. Of course, our algorithmic primitives and analysis must ensure that this view is indeed tree-like. Once we established this, we could bypass the technical intricacies of prior work.

Our algorithm progressively finds a better approximation of the current approximate matching. We implement that by dividing our augmentation search into different scales. A fixed scale guides the granularity of the search of the rest of the algorithm, and the scale values range from $1/2$ to $O(1/{ϵ}^2)$ in powers of $2$. Each scale is further divided into many phases.

Our pass complexity balances and ties several parameters guiding the algorithm. These parameters are the number of edge-label reductions, the sizes of alternating trees, the scale values, and the number of phases in a scale. The most important of these parameters are scale and the upper bound on an alternating tree size.

When phases are executed for a given scale $h$, the attempt is to arrive at a $(1+O(h/ϵ))$-approximate maximum matching. Hence, in the beginning, when there are many augmentations, large values of $h$ imply that the algorithm will soon arrive at the desired approximation. Importantly, this also means that fewer augmenting paths must be found for the next scale, i.e., scale $h/2$, because scale $h/2$ starts with a better approximation than scale $h$. Therefore, scales enable us to balance the quality of approximation we want to achieve with the number of augmentations that must be found: the tighter the approximation requirement is, the slower the algorithm is; the fewer the augmentations must be found, the faster the algorithm is.

A fundamental difference between our approach and that of [48] is that the search structure from a free vertex can be seen as a tree that we also refer to by structure. The same as in [48], in our work, DFS structures $S_{\alpha }$ and $S_{\beta }$ originating at different free vertices $\alpha$ and $\beta$ might affect each other – either by moving a part of $S_{\alpha }$ to $S_{\beta }$ via Overtake, or by finding an augmentation between $\alpha$ and $\beta$. In [48], these structures and blossoms are represented as a union of alternating paths, with some edges being marked as belonging to odd cycles. There is no special treatment of blossoms, nor do those structures have any particular shape. On the other hand, we represent these structures as alternating trees; some vertices in those trees might correspond to blossoms. Crucially, it enables us to simplify structure-related procedures, provide a simpler proof of correctness, and prove new properties about structure sizes, allowing us to significantly reduce the pass complexity.

Finally, we believe the complexity of [48] can be reduced to $O(1/{ϵ}^{16})$ by a slightly more careful analysis and tweaking parameters. Adding the scales would improve the exponent in the pass-complexity by an additional $2$. In addition, replacing “a maximal set of augmenting paths” with “the maximum set of augmenting paths” in the complexity analysis in [48] would result in yet another improvement by $2$ in the exponent of pass-complexity (e.g., using Lemma 6.2 in the full version). Nevertheless, it is unclear that, unless fundamental changes are made in the approach, [48] can result in a pass-complexity better than $O(1/{ϵ}^{12})$.

In the following, we will sketch our algorithm, incrementally providing more details. Algorithm 1 gives a high-level description of the algorithm. Recall that $\frac{1}{ϵ}$ is assumed to be a power of $2$.

Algorithm 1 provides an outline of our approach. Algorithm˜1 applies a simple greedy algorithm to find a maximal matching, which is a 2-approximation for the problem. Starting from this maximal matching, our algorithm repeatedly finds augmenting paths to improve the current matching. This is done by executing several phases with respect to different scales, detailed as follows.

Each iteration of the for-loop in Algorithm˜1 corresponds to a scale $h$. In one scale $h$, each iteration of the for-loop in Algorithm˜1 is called a phase with respect to the scale $h$. In each phase, the procedure Alg-Phase is invoked to find a set $𝒫$ of vertex-disjoint augmenting paths. In the execution of Alg-Phase, we may conceptually remove some vertices from $G$. After the execution of Alg-Phase, Algorithm˜1 restores all removed vertices to $G$. After this step, $G$ is identical to the input graph. Then, Algorithm˜1 augments the current matching using the set $𝒫$ of vertex-disjoint augmenting paths, which increase the size of $M$ by $|𝒫|$.

The scale $h$ is a parameter that determines the number of phases executed and the number of passes spent on each phase. By passing a smaller scale to Alg-Phase, Alg-Phase would spend more passes attempting to find more augmenting paths in the graph. Our algorithm decreases the scale gradually so that more and more augmenting paths in the graph can be discovered.

We now proceed to outline what the algorithm does in a single phase, whose pseudocode is given as Algorithm 2. In each phase, our algorithm executes DFS explorations from all free vertices in parallel. Details of the parallel DFS are described as follows. Algorithms˜2, 2, and 2 initialize the set of paths $𝒫$, the label of each arc, and the structure of each free vertex. The structure of a free vertex $\alpha$ is initialized to be an alternating tree of a single vertex $\alpha$. That is, $G_{\alpha }$ and ${\mathrm{\Omega }}_{\alpha }$ are set to be a graph with a single vertex $\alpha$ and a set containing a single trivial blossom $\{\alpha \}$, respectively; the working vertex $w_{\alpha }^{\prime }$ is initialized as the root of $T_{\alpha }^{\prime }$, that is, ${\mathrm{\Omega }}_{\alpha }(\alpha )$. Algorithm˜2 computes two parameters ${\mathrm{𝗅𝗂𝗆𝗂𝗍}}_h$ and ${\tau }_{\max }(h)$. The purpose of these two parameters is detailed later. The for-loop in Algorithm˜2 executes ${\tau }_{\max }(h)$ iterations, where each iteration is referred to as a pass-bundle. The execution of a pass-bundle corresponds to one step in the parallel DFS. Each pass-bundle consists of four parts:

1. (1)

   Algorithms˜2, 2, 2, and 2 initialize the status of each structure in this pass-bundle. A structure is marked as on hold if and only if it contains at least ${\mathrm{𝗅𝗂𝗆𝗂𝗍}}_h$ vertices. Each structure $S_{\alpha }$ is marked as not modified. The purpose of this part is described in Section 4.4.

2. (2)

   The procedure Extend-Active-Path makes a pass over the stream and attempts to extend each structure that is not on hold. Details of this procedure are given in the full version [72].

3. (3)

   After the execution of Extend-Active-Path, the subgraph $G_{\alpha }$ maintained in each structure $S_{\alpha }$ may change. The procedure Contract-and-Augment is then invoked to identify blossoms and augmenting paths. The procedure makes a pass over the stream, contracts some blossoms that contain the working vertex of a structure, and identifies pairs of structures that can be connected to form augmenting paths. Details of this procedure are given in the full version.

4. (4)

   The procedure Backtrack-Stuck-Structures examines each structure. If a structure is not on hold and fails to extend in this pass, Backtrack-Stuck-Structures backtracks the structure by removing one matched arc from its active path. Details of this procedure are given in the full version.

In the full version, we prove the following lemma, showing that all invariants presented in Sections 4.1.1 and 4.1.2 are preserved in the execution of Alg-Phase.

In the for-loop of Algorithm˜2, we mark a structure $S_{\alpha }$ on hold if and only if it contains at least ${\mathrm{𝗅𝗂𝗆𝗂𝗍}}_h$ vertices. See Algorithms˜2 and 2 of Algorithm 2. This operation plays a crucial role in our analysis of the pass-complexity of our algorithm. See the full version for details.

In the for-loop, we also mark each structure as not modified. Recall that each structure $S_{\alpha }$ is represented by a tuple $(G_{\alpha },{\mathrm{\Omega }}_{\alpha },w_{\alpha }^{\prime })$. In the execution of the pass-bundle, we may modify some structures by, for example, adding new arcs to $G_{\alpha }$. Whenever $G_{\alpha },{\mathrm{\Omega }}_{\alpha }$, or $w_{\alpha }^{\prime }$ is changed, we mark $S_{\alpha }$ as modified. In other words, if a structure $S_{\alpha }$ is marked as not modified, $(G_{\alpha },{\mathrm{\Omega }}_{\alpha },w_{\alpha }^{\prime })$ is unchanged since the beginning of the current pass-bundle.