We study the dynamic version of the maximum matching problem, a cornerstone of combinatorial optimization [Kuh55,Edm65b,Edm65a]. In the dynamic matching problem, the task is to build a data structure that, given a graph G with n vertices and m edges undergoing both edge insertions and deletions, maintains an (approximate) maximum matching of G or, in the value version, just the size of the maximum matching, denoted by µ(G). The goal is to minimize the update time required to update the solution after each edge change.
The first non-trivial algorithm for this problem was by Sankowski [San07] 15 years ago, which exactly maintains the maximum matching size using O(n 1.495 ) update time, which is recently improved to O(n 1.407 ) [BNS19]. Unfortunately, this latter bound is tight under the hinted OMv conjecture [BNS19]. Furthermore, in sparse graphs, even m 1-o(1) update time is required assuming the kcycle conjecture [PGVWW20]. These strong conditional lower bounds have shifted the attention of researchers to approximate matching. An α-approximate matching is a matching of size at least µ(G)/α. The following has become one of the holy-grail questions in the dynamic graph algorithms and fine-grained complexity communities [ARW17]: Question 1.1. Is there a dynamic (1 + ǫ)-approximate matching algorithm with polylogarithmic update time for an arbitrarily small constant ǫ?
The current state of the art is, however, still very far from this goal. A straightforward algorithm with O(n) amortized update time is to simply recompute a (1 + ǫ)-approximate matching from scratch in O(m) time [DP14] every after 2ǫm/n edge updates. 1 Surprisingly, this easy O(n) bound already captures the limitation of all known techniques! An improved algorithm with O( √ m) update time was given ten years ago by Gupta and Peng [GP13], but it still takes O(n) time in dense graphs. Very recently, Assadi et al. [ABKL23] showed how to obtain O(n/(log * n) Ω(1) ) update time, but their regularity-lemma-based approach inherently cannot give an improvement larger than a 2 Θ( √ log n) = n o(1) factor. Until now, no dynamic (1+ǫ)-approximate algorithms can break through the naive O(n) barrier by a polynomial factor. 2 Intensive research during the last decade instead showed how to speed up update time by relaxing the approximation factor. The influential work by Onak and Rubinfeld [OR10] gave the first dynamic matching algorithm with polylogarithmic update time that maintains a large constant approximate maximum matching. Then, Baswana, Gupta and Sen [BGS11] showed a dynamic maximal matching with logarithmic update time, which gives 2-approximation. A large body of work then refined this result in various directions, including constant update time [Sol16], deamortization [CS18,BFH19,Kis22], and derandomization [BHN16, ACC + 18, BK19, Waj20, BK21]. In 2015, Bernstein and Stein [BS15,BS16] showed a novel approach for maintaining a (3/2 + ǫ)-approximate matching using Õ(m 1/4 ) = Õ( √ n) update time. 3 Refinement of this approach and new trade-off results with approximation in the range (3/2, 2) were also intensively studied [BLM20, GSSU22, Kis22, BK22, RSW22]. All these techniques, however, seem to get stuck at (3/2)-approximation.
Very recently, the above long-standing trade-off was improved by Behnezhad [Beh23] and, independently, by Bhattacharya et al. [BKSW23] via a new connection to sublinear and streaming algorithms. To maintain maximum matching size, they gave 1.973-approximation algorithms with polylogarithmic update time, and, on bipartite graphs, Behnezhad [Beh23] pushed it further to (3/2 -Ω(1))-approximation in Õ( √ n) update time. While this new connection is very inspiring,
1 See Appendix C for the proof of this simple algorithm. 2 In contrast, in the partially dynamic setting where graphs undergo edge insertions only or edge deletions only, there are many algorithms with polylogarithmic amortized update time [GRS14, GLS + 19, BGS20, JJST22, BKSW23]. 3 We use Õ(•) to hide polylog(n) factor throughout the paper.
it has been a key open problem [BRRS23] whether non-trivial (1 + ǫ)-approximate matching algorithms in dense graphs exist in the sublinear model. Hence, it remains unclear whether an improved dynamic (1 + ǫ)-approximation algorithm is possible via this new connection or even possible at all. Indeed, in this paper, we give the first dynamic (1 + ǫ)-approximate matching size algorithm that finally improves the O(n) bound by a polynomial factor, formally stated below.
Theorem 1.2. There is a dynamic (1 + ǫ)-approximate matching size algorithm with m 0.5-Ωǫ(1) worst-case update time.
The algorithm is randomized and works against an adaptive adversary with high probability. Moreover, the algorithm maintains (1 + ǫ)-approximate matching M of G in the sense that, given a vertex v, it can return a matched edge (v, v ′ ) ∈ M or ⊥ if v / ∈ V (M ) in m 0.5+f (ǫ) time, where f is an increasing function such that f (ǫ) → 0 when ǫ → 0.
It has been asked repeatedly [GP13,BS15,BS16] whether there exists a dynamic (1 + ǫ)approximate matching algorithm with m 0.5-Ωǫ(1) update time. Theorem 1.2 thus gives an affirmative answer to the value version of this open question. Although the matching is not explicitly maintained in Theorem 1.2, it still supports queries whether a vertex is matched or not. The recent algorithms that only maintain the estimate of µ(G) by [Beh23,BKSW23] inherently cannot support this query.
We obtain Theorem 1.2 by making progress in sublinear algorithms: we show the first sublinear (1, ǫn)-approximate matching algorithm with truly sublinear time even in dense graphs. Here, an (α, β)-approximate matching means a matching of size at least µ(G)/α-β. Given our new sublinear matching algorithm summarized below, Theorem 1.2 follows using known techniques.
Theorem 1.3. There is a randomized algorithm that, given the adjacency matrix of a graph G, in time n 2-Ωǫ(1) computes with high probability a (1, ǫn)-approximation μ of µ(G).
After that, given a vertex v, the algorithm returns in n 1+f (ǫ) time an edge
where M is a fixed (1, ǫn)-approximate matching, where f is an increasing function such that f (ǫ) → 0 when ǫ → 0.
We note that the additive approximation factor in Theorem 1.3 is unavoidable for sublinear algorithms with access to only the adjacency matrix: checking whether there is zero or one edge requires Ω(n 2 ) adjacency matrix queries.
Behnezhad et al. [BRRS23] posted an open question about sublinear matching algorithms as follows "ruling out say a 1.01-approximation in n 2-Ω(1) time would also be extremely interesting."foot_0 . Since the additive approximation factor is unavoidable for algorithms using the adjacency matrix only, the analogous question becomes whether one can rule out a (1, n/100)-approximation in n 2-Ω(1) time. Theorem 1.3 answers this question negatively since we can get arbitrarily good additive approximation in n 2-Ω(1) time.
To put Theorem 1.3 into the larger context of sublinear matching literature, let us discuss its history below. We use ∆ and d to denote the maximum and average degree of the graph respectively.
Approximating µ(G). One of the main goals in this area, initiated by Parnas and Ron [PR07], is to approximate the size of maximum matching µ(G) in sublinear time when given access to the adjacency list and matrix of an input graph. Early research on this topic focused on obtaining O(1) time algorithms when ∆ = O(1). However, these early work [PR07, NO08, YYI12] may require Ω(n 2 ) time on general graphs. This drawback was first addressed in [KMNFT20] and [CKK20] (based on [ORRR12]), both of which were then subsumed by the algorithms of Behnezhad [Beh22] that compute a (2, o(n))-approximation in Õ(d+1) time. His algorithms are near-optimal and settle the problem in the regime of approximation ratio at least 2.
Subsequent work focuses on optimizing the approximation ratio within n 2-Ω(1) time. To compare with Theorem 1.3, let us discuss only algorithms that use the adjacency matrix. Behnezhad et al. [BRRS23] first broke the 2-approximation barrier by computing a (2 -Ω γ (1), o(n))-approximate matching in Õ(n 1+γ ) time. Then (3/2, ǫn)-approximation algorithms with n 2-Θ(ǫ 2 ) time were shown independently in [BKS23,BRR23]. Behnezhad et al. [BRR23] improved this further to (3/2 -Ω(1), o(n))-approximation in n 2-Ω(1) time on bipartite graphs. 5 We summarize the previous work in Table 1.
By the first part of Theorem 1.3, we show that even (1, ǫn)-approximation is possible in n 2-Ωǫ(1) time. As we mentioned, this result addresses the open question of [RSW22]. It remains very interesting to see an optimal approximation-time trade-off for this problem.
Matching Oracles. In the area of local computation algorithms (LCA), initiated by Robinfeld et al. [RTVX11,ARVX12], we want a matching oracle for some fixed approximate matching M such that, given any vertex v, return
The goal is to optimize the approximation ratio of M and minimize the worst-case query time over all vertices. Note that, given a matching oracle for an α-approximate matching, we can compute (α, ǫn)-approximation of µ(G) by simply querying the oracle at O(1/ǫ 2 ) random vertices. So this is stronger than the previous goal.
The worst-case guarantee over all vertices is stronger than the expected query time for each vertex [NO08] or for just a random vertex [YYI12,Beh22], which is even weaker. This strong guarantee is useful for bounding the query time of adaptive queries, which depend on answers of the previous queries, and is crucial in some applications [LRV22]. Our approach for "boosting" the approximation ratio also requires adaptive queries and hence needs worst-case guarantees.
A long line of work [RTVX11, ARVX12, RV16, LRY15, Gha16, GU19, Gha22] focused on building an oracle for maximal independent sets (which implies a 2-approximate matching oracle) and culminated in an oracle by Ghaffari [Gha22] that uses poly(∆ log n) query time with high probability. Levi et al. [LRY15] also a showed (1 + ǫ)-approximate matching oracle with ∆ O(1/ǫ 2 ) polylog(n) query complexity. However, all these algorithms are not sublinear in dense graphs. In this regime, the only non-trivial matching oracle was by Kapralov et al. [KMNFT20] and has Õ(∆) query time, but the approximation ratio is only a large constant and is in expectation. We summarize the previous work in Table 2.
The second part of Theorem 1.3 gives the first non-trivial matching oracle on dense graphs whose multiplicative approximation ratio is a small constant, which is 1 in our case, but we need to pay additive approximation factor. Summary. Our main result, Theorem 1.2, is the first dynamic (1 + ǫ)-approximate matching size algorithm with m 0.5-Ωǫ(1) update time, breaking through the naive yet long-standing O(n) barrier by a polynomial factor. Our key technical component, Theorem 1.3, makes progress in the area of sublinear-time matching algorithms on dense graphs. Among algorithms for approximating µ(G) only, we improve the best approximation ratio from (3/2-Ω(1), o(n)) by [BRR23] to (1, ǫn). Among LCAs, it is the first one on dense graphs whose multiplicative approximation is a small constant.
Organization. First, we give an overview of our algorithms in Section 2. Then, we set up notations and give preliminaries in Section 3. In Section 4, we present a key building block which is a matching oracle for an induced graph G[A] where A is unknown to us. Using this, we show in Section 5 how to boost the approximation ratio of any matching oracle. By repeatedly boosting the approximation ratio, we give a (1, ǫn)-approximate matching oracle (Theorem 1.3) in Section 6. Finally, we combine this oracle with known techniques in dynamic algorithms to Theorem 1.2 in Section 7.
We would like to thank David Wajc for suggesting the implementation of McGregor's algorithm in the sub-linear model.
Our high-level approach is based on the interconnection between dynamic, sublinear, and streaming algorithms. This connection differs from the ones used in the recent results of [BKSW23,Beh23]. For example, the dynamic (2 -Ω(1))-approximate algorithms in [BKSW23,Beh23] are inspired by the two-pass streaming algorithms (e.g. [KMM12]). Then, they use sublinear algorithms [Beh22] to implement this streaming algorithm in the dynamic setting efficiently. 6 In contrast, it is our sublinear algorithm, not dynamic algorithm, that is inspired by the O(1)-pass streaming algorithm [McG05]. Below, we explain the overview of our sublinear algorithm, which consists of two key ingredients, and then explain how our dynamic algorithm easily follows.
Ingredient I: Reduction from (1, γn)-Approximation to Arbitrarily Bad Approximation.
An initial observation is that the streaming algorithm by McGregor [McG05] can be viewed as the following reduction: one can compute a (1 + γ)-approximate matching by making O γ (1) calls to a subroutine that, given S ⊆ V , returns a O(1)-approximate matching of the induced subgraph G[S].
We observe that a much weaker subroutine suffices when additive approximation is allowed. Let LargeMatching(S, δ) be a subroutine that, given S ⊆ V and δ, returns a matching
Note that the approximation of M can be arbitrarily bad depending of δ. By adapting McGregor's algorithm, we show how to compute a (1, γn)-approximate matching using only t = O γ (1) calls to LargeMatching(S 1 , δ 1 ), . . . , LargeMatching(S t , δ t )
where each δ i is a small constant depending on γ. This algorithm, denoted by Alg(γ), is our template algorithm (detailed in Section 5.1), which we will try to implement in the sublinear setting.
Additionally, we observe that each vertex set S i can be determined in a very local manner. More precisely, a membership-query of the form "is a vertex v ∈ S i ?" can be answered by making only q = O γ (1) matching-queries of the form "is a vertex u ∈ V (M j )? if so, return (u, u ′ ) ∈ M " where j < i and M j is the output of LargeMatching(S j , δ j ) previously computed.
However, the big challenge in the sublinear model, unlike the streaming model, is that even the weak subroutine like LargeMatching(•) is impossible. 7 Even worse, if we could not compute each matching M j explicitly for j < i, then how can we answer a membership-query whether v ∈ S i ? Note that known sublinear algorithms for estimating the matching size of G[S] are not useful here.
The above obstacle leads us to our second ingredient. We show that at least the oracle version of LargeMatching(•) can be implemented in the sublinear model. Later, we will explain why it is strong enough for implementing the template algorithm Alg(γ) in the sublinear model.
Ingredient II: Large Matching Oracles on Induced Subgraphs. Suppose that a vertex set A ⊆ V is unknown to us but a membership-query of A, i.e., checking if v ∈ A, can be done in n 1+ǫ time. Given access to the adjacency matrix of G, we show how to construct an oracle LargeMatchingOracle(A, δ, ǫ) with the following guarantee: Using Õδ n 2-ǫ preprocessing time, we obtain an oracle that supports matching-queries for a matching M in G[A] with Õδ n 1+g(ǫ) query time where
The main challenge of implementing LargeMatchingOracle(A, δ, ǫ) in the sublinear model is that we want to find a large matching on the induced subgraph G[A]. The challenge comes from possible Ω(n 2 ) edges between A and V \ A, and we must avoid reading these edges to get sublinear time. It turns out that this challenge can be overcome. We use the idea that appeared before in the algorithm of [BRR23] in a different context of estimating (3/2 -Ω(1))-approximation µ(G) on bipartite graphs. See the details in Section 4.
Given the above two ingredients, we can combine them to get our main results in the sublinear and dynamic settings, as follows.
Result I: (1, γn)-Approximate Matching Oracles in n 2-Ωγ (1) Time. Now, we show how to implement the template algorithm Alg(γ) in n 2-Ωγ (1) time. Let ǫ ∈ (0, 1) be a small constant where lim γ→0 ǫ = 0. Let ǫ 0 = ǫ and ǫ i = g(ǫ i-1 ) for all i ∈ [1, t] where g is the function in the guarantee of Ingredient II. So ǫ = ǫ 0 ≤ ǫ 1 ≤ • • • ≤ ǫ t and lim γ→0 ǫ t = 0.
We simply replace each call to LargeMatching(S i , δ i ) with LargeMatchingOracle(S i , δ i , ǫ i-1 ). Now, by induction on i ∈ [1, t], we will show that we can support membership-queries for S i in Õγ n 1+ǫ i-1 time and matching-queries for M i in Õγ n 1+ǫ i time. Let us ignore the base case as it is trivial. For the induction step, we have the following:
1. To answer a membership-query for S i , the template algorithm only needs to make q = O γ (1) matching-queries to M j where j < i. So the total query time is q • Õγ (n 1+ǫ i-1 ) = Õγ (n 1+ǫ i-1 ).
2. To answer a matching-query for M i , the oracle LargeMatchingOracle(S i , δ i , ǫ i-1 ) for the matching M i has query time Õγ n 1+g(ǫ i-1 ) = Õγ n 1+ǫ i .
The total preprocessing time we need for LargeMatchingOracle(•) to implement all the t rounds is
. At the end of the last round, we can support matchingqueries for the (1, γn)-approximate matching M returned by Alg(γ) in Õγ (n 1+ǫt ) time, where lim γ→0 ǫ t = 0.
To get a (1, γn)-approximate estimate μ of µ(g), we sample Õ(1/γ 2 ) vertices and check if they are matched under M . Whp, this is a (1, Θ(γ)n)-approximation of µ(G) because M is (1, γn)approximate.
Result II: Dynamic (1 + γ)-Approximate Matching Size.
Our dynamic matching size algorithm now follows from standard techniques. Using the well-known vertex reduction technique (see, for example, Corollary 4.9 of [Kis22]), we can assume that µ(G) ≥ γn at all times. We work in phases, where each phase lasts for γ 2 n updates. At the start of each phase, we invoke the sublinear algorithm from Result I above, to obtain a (1, γ 2 n)-approximate estimate μ of µ(G), in n 2-Ωγ(1) time. Since µ(G) ≥ γn and since the phase lasts for only γ 2 n updates, this μ continues to remain a purely multiplicative (1+Θ(γ))-approximate estimate of µ(G) throughout the duration of the phase. This leads to an amortized update time of n 2-Ωγ(1) /(γ 2 n) = n 1-Ωγ (1) . In Section 7, we show how to extend this approach to prove Theorem 1.2.
Unless speficied otherwise, the input graph G = (V, E) will have n nodes and m edges. A matching M ⊆ E is a subset of edges that do not share any common endpoint. We use the symbol µ(G) to denote the size of a maximum matching in G. We say that a pah p = (v 0 , v 1 , . . . , v i ) is an alternating path in G w.r.t. a matching M ⊆ E iff (v j , v j+1 ) ∈ E for all j ∈ [0, i -1] and the edges in the path p alternate between being in M and in E \ M . We say that p is an augmenting path in G w.r.t. M iff p is an alternating path whose first and the last edges are both unmatched in M . The length of a path is the number of edges in it. We let V (M ) denote the set of matched nodes in a matching M ⊆ E. Consider any node v ∈ V (M ) and suppose that (u, v) ∈ M . Then we say that u is the mate of v in M . Given a subset of nodes S ⊆ V , G[S] denotes the subgraph of G induced by S. Given any graph G ′ , the symbol E(G ′ ) denotes the set of edges in G ′ .
Throughout the paper, the symbol Θ k,γ (1) will denote any positive constant that depends only on k and γ (where k and γ are constant parameters whose values will be chosen later on). We analogously use the notation Θ k (1) to denote a constant that depends only on k. Finally, the symbol Õ(.) will be used to hide any polylog(n) factors.
Oracles. We have the adjacency matrix access to the input graph G. Each query takes O(1) time. We do not have the adjacency list access to the input graph.
For any vertex set A ⊂ V , an A-membership oracle mem A : V → {0, 1} indicates whether v ∈ A for any v ∈ V . That is, we have mem A (v) = 1{v ∈ A}.
A matching oracle match M : V → V 2 ∪ {⊥} for a matching M is an oracle that, given a vertex v ∈ V , returns
Similarly, a mate oracle mate M : V → V ∪ {⊥} for a matching M is an oracle that, given a vertex v ∈ V , returns
Concentration Bounds. We need standard concentration bounds as follows.
Proposition 3.1 (Hoeffding bound). Let X 1 , . . . , X n be independent random variables such that a ≤ X i ≤ b. Let X = n i=1 X i . For any t > 0,
Proposition 3.2 (Chernoff bound). Let X 1 , . . . , X n be independent {0, 1}-random variables. Let X = n i=1 X i where E[X] ≤ µ For any t > 0 where t ≤ µ,
Chernoff bound can be much stronger than Hoeffding bound when E[X] has small upper bound. For example, if we applied Proposition 3.1 to the setting for Proposition 3.2, we would only get that the bound of 2 exp(-2t 2 3n ) which is much weaker than 2 exp(-t 2 3µ ) when µ ≪ n.
In this section, we present the key subroutine of this paper. The goal is to construct a matching oracle for an induced subgraph G[A] but A is unknown to us; we only have access to an A-membership oracle mem A .
Theorem 4.1. Let G = (V, E) be a graph, A ⊆ V be a vertex set. Suppose that we have access to adjacency matrix of G and an A-membership oracle mem A with t A query time. We are given as input ǫ > 0 and δ in > 0.
We can preprocess G in Õ((t A + n)(n 1-ǫ + n 4ǫ )/poly(δ in )) time and either return ⊥ or construct a matching oracle match M (•) for a matching M ⊂ G[A] of size at least δ out n where δ out = δ 5 in /10 8 that has Õ((t A + n)n 4ǫ /poly(δ in )) worst-case query time. If µ(G[A]) ≥ δ in n, then ⊥ is not returned. The guarantee holds with high probability.
The very important property of Theorem 4.1 is that it makes n 1-ǫ oracle calls to mem A during preprocessing and only n O(ǫ) calls to mem A on each query. The rest of this section is devoted for proving Theorem 4.1.
To prove Theorem 4.1, we adapt the technique used inside the algorithm by Behnazhad et al. [BRR23] for (3/2 -Ω(1))-approximating µ(G) on bipartite graphs. We observe that the idea there has reach beyond (3/2 -Ω(1))-approximation algorithms. The abstraction of that idea leads us to Theorem 4.1, the crucial subroutine for later parts of our paper.
This section is organized as follows. In Section 4.1, we show a weaker version of Theorem 4.1 that works well on low degree graphs. We will use this weaker version in the preprocessing step, described in Section 4.2. Then, we complete the query algorithm in Section 4.3.
Here, we show a similar result as Theorem 4.1, but it is efficient only when the maximum degree ∆ is small. In particular, the query algorithm makes n O(ǫ) calls to mem A only when ∆ = n O(ǫ) . Lemma 4.2. Let G = (V, E) be a graph with maximum degree ∆ where ∆ is known and A ⊆ V be a vertex set. Suppose that we have access to adjacency matrix of G and an A-membership oracle mem A with t A query time. We can construct in Õ((t
The proof of Lemma 4.2 is based on the the following (2, ǫn)-approximate matching oracle given access to adjacency list. Lemma 4.3 is proved by combining an improved analysis of randomized greedy maximal matching of Behnezhad [Beh22] into a framework for constructing an LCA by [LRY15]. We do not claim any novel contribution here and defer the proof to Appendix A. Now, to prove Lemma 4.2, we need to strengthen Lemma 4.3 in two ways. First, it must work with the adjacency matrix, not the adjacency lists. Second, it must return a large matching of an induced subgraph G[A], not that of G. However, this can be done using a simple simulation.
Proof of Lemma 4.2. Let A denote the algorithm of Lemma 4.3. We simulate A on G[A] with parameter d ← ∆ as follows.
Whenever A needs to sample a vertex, we sample O(log(n)/ǫ) vertices in G and call mem A on each of them. If one of them is in A, then we get a random vertex in G[A]. If none of them is in A, then w.h.p. |A| ≤ ǫn. If this ever happens, even an empty matching is a (2, ǫn)-approximate matching in G[A], and the problem becomes trivial.
Whenever A needs to make queries to the adjacency list of any vertex v, we can construct the whole adjacency list of v in G[A] by first making n adjacency matrix queries to learn all neighbors of v in G and then makes deg(v) ≤ ∆ oracles calls to mem A to know which neighbors are in G[A]. This takes O(t A ∆ + n) time. Every other computation can be simulated without the overhead.
Therefore, each step of A can be simulated with an extra
We describe the preprocessing algorithm in Algorithm 1 with the guarantees summarized in the lemma below.
that satisfies one of the following:
The algorithm also reports which properties above M ′ satisfies. If µ(G[A]) ≥ δ in n, then ⊥ is not returned with high probability.
In Algorithm 1, the remaining set V ′ is initialized as V and only shrinks. For convenience, we let A ′ := A ∩ V ′ and D ′ := D ∩ V ′ denote the remaining alive and dead vertices.
In this part, we prove the correctness of Algorithm 1 assuming that it does not return ⊥. We first show that μ1 and μ2 are good approximation of M i [A] and M i base on basic there definition and Hoeffding's bound.
Lemma 4.5. For every i, we have
and by Hoeffding bound Proposition 3.1, we have
Repeat the following for T times:
1. Sample kp distinct pairs of vertices from V ′ . Partition the sampled pairs into (P 1 , . . . , P k )
where each P i is an ordered list containing p pairs of vertices.
(b) Let M i be the greedy maximal matching when scanning E i in order. \\Case 1:
\\Case 2:
Return ⊥ (Error).
Lemma 4.6. For every i, we have
Proof. The probability that a random vertex from
2r 2 -δoutn 2 and by Hoeffding bound Proposition 3.1, we have
Next, we show the "sparsification" property of randomized greedy maximal matching
should not exist because it should have been matched by M i via one of the sampled edges. The proof is similar to Lemma 3.1 of [BFS12], which considers this sparsification property of the randomized greedy maximal independent set, instead of maximal matching.
Lemma 4.7. For every i, the maximum degree of
Proof. Let us describe an equivalent way to construct M i . Initialize M i = ∅ and then sample p pairs of vertices in V ′ . For each sampled pair
and both u and v are not matched by M i , then we add (u, v) into M i . At the end of this process, we will show that, for any
, let M i t denote the matching M i after we sampled the t-th pair. For convenience, we denote
as the degree of v at time t. We want to show that Pr[deg
, the probability that v remained at unmatched after time t is
In particular, the probability that
From the above lemmas, we can conclude the correctness of the algorithm.
Corollary 4.8. If Algorithm 1 returns a matching M ′ , then M ′ satisfies the guarantees from Lemma 4.4 w.h.p.
Proof. If M ′ is returned under Case 1. Then, by Lemma 4.5, we have
In this part, we show that if µ(G[A]) ≥ δ in n, then Algorithm 1 does not return ⊥ w.h.p. For any graph G and
Our high-level plan is that we will show that D ′ decreases its size by Θ(δ 2 in n) in each iteration in the repeat loop. So D ′ must become very small after T = Θ(1/δ 2 in ) iterations. But when this happens, we can show that either Case 1 or Case 2 must happen and so the algorithm must terminate without error.
To carry out the above plan, we need a helper lemma (Lemma 4.9) which states that, even if V ′ keeps shrinking, the maximum matching in G[V ′ ] remains large, µ(G[A ′ ]) ≥ δ in n/2. We will need this fact throughout the whole argument.
The high-level argument goes as follows. If the algorithm does not return M ′ , then M i [A ′ ] is very small for all i and so G[A ′ ] contains few edges. It follows that the set C of removed vertices contains only few vertices in
. Thus, we remove only few vertices from A ′ and so the size of µ(G[A ′ ]) cannot decrease too much. The formal argument below goes through the set A ′ sp and the above paragraph gives the right intuition.
, if the algorithm does not terminate yet.
Proof. We prove by induction on τ . For τ = 0 (i.e. the beginning the algorithm), the claim holds as µ(G[A]) ≥ δ in n. Next, we consider τ ≥ 1. By induction hypothesis, at the beginning of the τ -th iteration, we have
) is a sum of r 3 independent random variable whose range is k (since the maximum degree in G and G[A ′ ] is k), by Hoeffding bound Proposition 3.1, we have
. This means that we remove at most δ in n 2T vertices from A ′ at the end of the τ -th iteration. So the size of maximum matching in G[A ′ ] may decrease by at most δ in n 2T . Thus,
Given Lemma 4.9, we will use the following lemma to argue that if Algorithm 1 does not return M i , then then M i must match many vertices between A ′ and D ′ .
Proof. Let M * be the maximum matching in G[A ′ ] of size at least δ in n/2. We partition edges in M * into two parts:
Lemma 4.10 also says that once D ′ become small enough, Algorithm 1 will not err w.h.p.
approximate matching. So μ2 ≥ 6δ out w.h.p. by Lemma 4.6. In either cases, so Algorithm 1 must return a matching M ′ at Line 2f or Line 2k. Now, we are ready to show that D ′ must shrink significantly after each iteration of the repeat loop, which means that there cannot be too many iterations before the algorithm terminate by Corollary 4.11. Lemma 4.12.
There are two main claims in the proof of Lemma 4.12. We suggest the reader to skip the proofs of these claims and see how they are used to prove Lemma 4.12 first.
Proof. At the end of the τ -th iteration, since Algorithm 1 did not terminate at Step 2f nor Step 2k, we have, w.h.p., that M [A ′ ] < 3δ out n by Lemma 4.5 and
and we have that
| is a sum of r 3 independent random variable whose range is k (since the maximum degree in G and G[A ′ ] is k), by Hoeffding bound Proposition 3.1, we have
Proof. We have
applying by Chernoff bound Proposition 3.2 where t = 1000 log n and µ = 1000 log nfoot_4 , we have
Now, let us prove Lemma 4.12 using the above claims.
Proof of Lemma 4.12. Observe that
where the inequality holds w.h.p. by Claim 4.14. Since |D ′ \ C| ≤ n and η = δ 2 in log(n)/10, we have by Claim 4.13 that
and so |D ′ ∩ C| ≥ δ 2 in 100 n as desired. Finally, we give the conclusion of this part.
/2 w.h.p. by Lemma 4.9. So, by Lemma 4.12 D ′ decreases its size by δ 2 in n/100 in each iteration in the repeat loop. Hence, we have that |D ′ | ≤ δ in n/3 before T = 100/δ 2 in iterations. Therefore, there is an iteration τ ∈ [1, T ] where Algorithm 1 will return a matching M ′ w.h.p. by Corollary 4.11.
Consider the (2, δ out n)-approximate matching oracle match low (•) in Line 2g, which is given graph
By Lemma 4.7, we can assume w.h.p. that G[V ′ \ V (M i )] has degree at most n 2ǫ . Lemma 4.2 implies the following: Proposition 4.16. Both preprocessing and query time of match low (•) is at most Õ((t
Lemma 4.17. Algorithm 1 takes Õ((t A + n)(n 1-ǫ + n 4ǫ )/poly(δ in )) total running time.
Proof. We will analyze the total running time for each iteration of the repeat-loop in Algorithm 1.
Since there are T = O(1/δ 2 in ) iterations and we assume δ in ≥ 1/poly log n, the running time is the same up to polylogarithmic factor. Now, fix one iteration of the repeat-loop.
The total time to compute M i , for all i ≤ k, is Θ(kp) = Õ(n 2-ǫ ). For each for-loop iteration, to compute μ1 , we make Θ(r 1 ) queries to mem A taking Θ(r 1 ) • t A = Õ(t A /δ 10 in ) time. To compute μ2 , we make r 2 queries to match low (•). By Proposition 4.16, this takes time
δ 25 in ) by Lemma 4.2. Next, we analyze the time to compute A ′ sp . Since |A ′ | ≥ δ in n w.h.p. by Lemma 4.9, we can sample a random vertex in A ′ by sampling at most O(log n/δ in ) times in V ′ w.h.p. For each sample, we need to make a query to mem A , so we can compute A
To conclude, the total running time in each iteration of the repeat-loop at most
The main lemma on preprocessing, Lemma 4.4, is implied by combining Corollary 4.8, Corollary 4.15 and Lemma 4.17
We define our matching oracle match depending on the cases from Lemma 4.4.
Suppose Lemma 4.4 returns
The algorithm for outputting match(v) with respect to M 1 is described in Algorithm 2. The correctness is straightforward and the worst-case query time is clearly 9 The algorithm for outputting match(v) with respect to M 2 is described in Algorithm 3. The correctness is straightforward. Let us analyze the query time.
Step 1 takes t A + O(1) time.
Step 2 takes Õ((t A + n)n 4ǫ /δ 3 out ) following the same proof as in Proposition 4.16 (the maximum degree of G[V ′ \ V (M ′ )] is at most n 2ǫ w.h.p. by Lemma 4.7).
Algorithm 3 Compute match(v) with respect to M 2 . Let match low be the (2, δ out n)-approximate matching oracle from Lemma 4.2 when given graph
In both cases, the matching oracle match respects a matching of size at least δ out n and has worst-case query time at most Õ((t A + n)n 4ǫ /poly(δ in )) w.h.p.
Recall the notations from Section 3. Throughout this section, we use the following parameters.
) is a sufficiently large integral constant that depends only on k and γ (see Lemma 5.12), and ǫ in > 0 is a sufficiently small constant such that 9 T • ǫ in < 1/5.
We present an algorithm Augment(G, M in , k, γ, ǫ in ), which takes as input: a graph G = (V, E) with n nodes, the parameters k, γ, ǫ in as in Definition 5.1, and an oracle match M in (.) for a matching M in in G that has Õk,γ (n 1+ǫin ) query time. The algorithm either returns an oracle match M out (.) for a matching M out in G that is obtained by applying a sufficiently large number of length (2k + 1)augmenting paths to M in , or it returns Failure. We now state our main result in this section.
Theorem 5.2. Set ǫ out := 9 T • ǫ in (see Definition 5.1). Given adjacency-matrix query access to the input graph G = (V, E), the algorithm Augment(G, M in , k, γ, ǫ in ) runs in Õk,γ n 2-ǫin time. Further, either it returns an oracle match M out (.) with query time Õk,γ (n 1+ǫout ), for some matching
• n (we say that it "succeeds" in this case), or it returns Failure. Finally, if the matching M in admits a collection of γ • n many node-disjoint length (2k + 1)-augmenting paths in G, then the algorithm succeeds whp.
In Section 5.1, we present a template algorithm for the task stated in Theorem 5.2. This is inspired by an algorithm of McGregor [McG05] for computing a (1 + ǫ)-approximate matching in the semi-streaming model.While describing the template algorithm, we assume that we are given the matching M in explicitly as part of the input, and that we need to either construct the matching M out or return Failure. Note, however, that in the sublinear setting, we cannot assume this.
Subsequently, in Section 5.2, we show how to implement the template algorithm in the sublinear setting under adjacency-matrix queries, which leads to the proof of Theorem 5.2.
Remark on Oracles: Throughout this section, we will treat the oracle match M (.) as a data structure in the sublinear model, which returns the appropriate answer upon receiving a query. In contrast, we will treat the oracle mate M (.) as simply an abstract function, so that mate M (v) simply denotes the mate of v (if it exists) under M (see Section 3). Note that we can return the value of mate M (v) by making a single query to match M (v), without any additional overhead in time.
We denote the template algorithm simply by Augment-Template(G, M in , k, γ), as we do not need the parameter ǫ in to describe it. The parameter ǫ in will become relevant only in Section 5.2, when we consider implementing this algorithm in the sublinear setting.
As part of the input to the template algorithm, the n-node graph G = (V, E) and the matching M in are specified explicitly. The algorithm either returns an explicit matching M out in G of size
• n (we say that it "succeeds" in this case), or it returns Failure. If M in admits a collection of γ • n many node-disjoint length (2k + 1)-augmenting paths in G, then the template algorithm succeeds whp. This mimics Theorem 5.2. Furthermore, the template algorithm has access to a subroutine LargeMatching(S, δ), which takes as input a subset of nodes S ⊆ V and a small constant δ ∈ (0, 1), and either returns ⊥ or returns a matching M in G[S] such that |M | ≥ 1 10 8 • δ 5 • n. In addition, if µ(G) ≥ δ • n, then it is guaranteed that LargeMatching(G, δ) does not return ⊥. This mimics Theorem 4.1, with δ in = δ.
Random partitioning: We start by partitioning the node-set V into 2k + 2 subsets L 0 , . . . , L 2k+1 , as follows. For each v ∈ V , we place the node v into one of the subsets L 0 , . . . , L 2k+1 chosen uniformly and independently at random. We will refer to the subset L i as layer i of this partition. If v ∈ L i , then we will write ℓ(v) = i and simply say that the node v belongs to layer i.
Let p be an augmenting path of length (2k + 1) in G w.r.t. M in . Assign an arbitrary direction to this path, so that we can write p = (v 0 , v 1 , . . . , v 2k+1 ) w.l.o.g. Specifically, we have (v 2i , v 2i+1 ) ∈ E \ M in for all i ∈ [0, k], and (v 2i-1 , v 2i ) ∈ M in for all i ∈ [1, k]. We say that the path p survives the random partitioning iff v i ∈ L i for all i ∈ [0, 2k + 1].
Lemma 5.3. Consider any collection P of node-disjoint length (2k + 1)-augmenting paths in G w.r.t. M in . Let P * ⊆ P denote the subset of paths in P that survive the random partitioning. If
Proof. Each path p ∈ P survives the random partitioning with probability (2k + 2) -(2k+2) . Since |P| ≥ γ •n, by linearity of expectation, we get:
1)•n. Finally, we note that whether a given path p ∈ P survives the random partitioning or not is independent of the fate of the other paths in P. The lemma now follows from a Chernoff bound.
Motivated by Lemma 5.3, the template algorithm will only attempt to augment M in along those augmenting paths that survive the random partitioning. This leads us to introduce the notion of layered subgraphs of G, as described below. Intuitively, although the template algorithm does not know the set P * in advance, it can be certain that the sequence of edges in any length (2k + 1)augmenting path in P * appears in successive layered subgraphs (see Observation 5.6).
Given the nodes in V H , the edge-set E H ⊆ E is defined as follows. An edge (u, v) ∈ E belongs to
We next define the subgraph H := (V H , E H ). Finally, for each i ∈ [0, 2k], let G i := (V, E i ) be a bipartite subgraph of G, where
is the set of edges in E H between layer i and layer i + 1. Note that we have defined the subgraphs {G i } over the entire node-set V , although every edge in these subgraphs has both its endpoints in V H . This is done to simplify notations, as will become evident when we describe how to implement our algorithm in the sublinear setting. For each i ∈ [0, 2k + 1], we refer to the nodes in V i := L i ∩ V H as being relevant for the concerned layer.
We now state some key observations, which immediately follow from the description above.
Observation 5.4. For all i ∈ [1, 2k], we have V i ⊆ V (M in ).
Observation 5.5. For all i ∈ [0, k], we have
Thus, if i is even, then G i consists of all the edges from G that connect two relevant nodes across the concerned layers. In constrast, if i is odd, then G i consists of the edges from M in that connect two relevant nodes across the concerned layers.
Observation 5.6. Consider any augmenting path p = (v 0 , v 1 , . . . , v 2k+1 ) w.r.t. M in in G that survives the random partitioning. Then we have
Nested matchings: Fix any j ∈ [0, k], and for each i ∈ [0, j] consider a matching M 2i ⊆ E 2i in G 2i . We say that the sequence of matchings M 0 , M 2 , . . . M 2j is nested iff for all i ∈ [1, j] and all
Observation 5.7. Consider any sequence of nested matchings M 0 , M 2 , . . . , M 2k . Then there exists a collection of node-disjoint length (2k + 1)-augmenting paths of size |M 2k | w.r.t. M in in G.
which is constructed according to the following procedure.
• v 2k+1 ← v, and i ← 2k. (Note that v 2k+1 is at layer 2k + 1 and is matched under M 2k .)
• While i ≥ 0:
-
i ← i -1.
Since the sequence M 0 , M 2 , . . . , M 2k is nested, applying Observation 5.4 and Observation 5.5, we can show (by an induction on the number of iterations of the While loop) that p(v) is a length (2k + 1)augmenting path in G w.r.t. M in . Furthermore, it is easy to see that the paths {p(v)} v∈V (M 2k )∩V 2k+1 constructed in this manner are mutually node-disjoint. This implies the observation.
Important parameters: We fix a constant ψ ∈ (0, 1), which depends on k and γ, i.e., ψ = Θ k,γ (1), and is chosen to be sufficiently small (see Corollary 5.16). Next, for each i ∈ [0, k], we define:
Consider any matching M ′ between the nodes at layers 2i and 2i+1, where i ∈ [0, k]. Intuitively, the parameters ψ i and δ i will determine how large M ′ needs to be so as to make us "happy". Note that the values of δ i and ψ i decrease in a doubly exponential manner with i. This fact will be crucially used during the analysis in Section 5.1.2.
A relatively informal summary of the algorithm: Motivated by Observation 5.7, the template algorithm attempts to find a sequence of nested matchings ending at layer 2k. Specifically, the algorithm runs in iterations. At the start of a given iteration, we maintain a sequence of nested matchings M 0 , M 2 , . . . , M 2i up to some layer 2i, such that |M 2j | ≥ ψ j • n for all j ∈ [0, i]. If i = k, then by Observation 5.7 we can already identify a collection of ψ k •n = Θ k,γ (1)•n many node-disjoint length (2k + 1)-augmenting paths in G w.r.t. M in , and so we just apply those augmenting paths to M in and return the resulting matching M out . Henceforth, assume that i < k. We classify each node in V H as either alive or dead (at the start of the first iteration every node was alive). We also enforce the invariant that all the nodes currently matched in M 0 ∪ M 2 ∪ • • • ∪ M 2i are alive. During the current iteration, we attempt to find a large matching M ′ between the alive nodes in G 2i+2 , while ensuring that the sequence M 0 , M 2 , . . . , M 2i , M ′ remains nested. Specifically, we make a call to the subroutine LargeMatching(S, δ i+1 ), for an appropriate S ⊆ V 2i+2 ∪ V 2i+3 . Depending on the outcome of this call, we now fork into one of the following three cases.
The call to LargeMatching(S, δ i+1 ) returns a matching M ′ . Thus, we are guaranteed that
We set M 2i+2 := M ′ , i := i + 1, and proceed to the next iteration.
The call to LargeMatching(S, δ i+1 ) returns ⊥, and i = -1 (i.e., the sequence of matchings M 0 , M 2 , . . . , M 2i was empty). Here, we terminate the template algorithm and return Failure.
The call to LargeMatching(S, δ i+1 ) returns ⊥, and i ≥ 0. Here, we change the status of all the nodes in V (M 2i ) ∩ V 2i+1 , along with their matched neighbors under M in (who are at layer 2i + 2), from alive to dead. We then delete the matching M 2i , set i := i -1, and proceed to the next iteration.
We will need some more notations while working with this algorithm in Section 5.2. Accordingly, below we present a more detailed and technical description of the template algorithm, along with these additional notations. While going through the rest of this section, the reader will find it helpful to refer back to the informal description above, whenever necessary.
In each iteration t ≥ 1, we will compute a matching M (t) in the subgraph G σ(t) , where σ(t) ∈ {0, 2, 4, . . . , 2k}. The mapping σ : T → {0, 2, . . . , 2k} will be constructed in an online manner, i.e., we will assign the value σ(t) only during the t th iteration. We now describe the state of the algorithm at the end of any given iteration.
At the end of an iteration t, a subset of past iterations Λ (t) ⊆ [t] are designated as being active w.r.t. t. If Λ (t) = ∅, then we write Λ (t) := λ
(t) 0 , λ (t) 1 , . . . , λ
corresponds to the sequence M 0 , M 2 , . . . , M 2i in the discussion immediately after Observation 5.7. Thus, the algorithm satisfies the following invariants.
Invariant 5.8. We have stack(t) ≤ k, and σ λ (t) j = 2j for all j ∈ [0, stack(t)].
Invariant 5.9. The sequence of matchings M
For each layer i ∈ [0, 2k + 1], the set of relevant nodes V i is partitioned into two subsets: A i and D i . We refer to the nodes in A i as alive, and the nodes in D i as dead. We let A := 2k+1 i=0 A i and D := 2k+1 i=0 D i respectively denote the set of all alive and dead nodes, across all the layers. The next invariant states that every matched node in an active iteration is alive.
At the start of the first iteration (when t = 1), every relevant node is alive (i.e., A i = V i and D i = ∅ for all i ∈ [0, 2k + 1]). Subsequently, over time the status of a relevant node can only change from being alive to being dead, but not the other way round. Thus, with time, the set D keeps growing, where the set A keeps shrinking. We now explain how to implement a given iteration t. Implementing iteration t: Let i = stack(t -1). If Λ (t-1) = ∅, then we set i = -1. If i = k, then there will be no more iterations, i.e., the algorithm will last for only t -1 iterations. In this scenario, we know that the sequence of matchings M
Based on this sequence, we identify a collection of |M λ (t-1) k | many node-disjoint augmenting paths w.r.t. M in in G, augment M in along those paths (see Observation 5.7), and return the resulting matching M out . Accordingly, from now on we assume that i ≤ k -1.
During iteration t, we will attempt to find a large matching M ′ in G 2i+2 between two sets of nodes: A 2i+3 and C 2i+2 . Recall that A 2i+3 denotes the alive nodes at layer 2i + 3. We refer to C 2i+2 as the set of candidate nodes for iteration t. Intuitively, we pick as many nodes from V 2i+2 into the set C 2i+2 as possible, subject to two constraints: (i) if we append M ′ at the end of the sequence of matchings from the currently active iterations, then the resulting sequence will continue to remain nested, and (ii) the nodes in C 2i+2 are currently alive. This leads us to the following definition.
We now call the subroutine LargeMatching(C 2i+2 ∪ A 2i+3 , δ i+1 ), in an attempt to obtain a large matching in
The last equality holds because of Observation 5.5, and since C 2i+2 ⊆ V 2i+2 and A 2i+3 ⊆ V 2i+3 . We set σ(t) := 2i + 2. Now, we fork into one of the following three cases.
The call to LargeMatching(C 2i+2 ∪ A 2i+3 , δ i+1 ) returns a matching M ′ . Thus, we are guaranteed that
We set M (t) := M ′ , Λ (t) := Λ (t-1) ∪ {t} and stack(t) := stack(t -1) + 1. This implies that λ (t)
and λ (t) stack(t) := t. Henceforth, we refer to this iteration t as a forwarding iteration at layer (2i + 2). We now move on to the next iteration (t + 1).
The call to LargeMatching(C 2i+2 ∪ A 2i+3 , δ i+1 ) returns ⊥, and i = -1. Here, the algorithm terminates and returns Failure.
The call to LargeMatching(C 2i+2 ∪ A 2i+3 , δ i+1 ) returns ⊥, and i ≥ 0. Here, we set M (t) := ∅. We also change the status of all the nodes in C 2i+2 , along with their matched neighbors under M in (who are at layer 2i+ 1), from alive to dead, and respectively move these nodes from A 2i+1 to D 2i+1 and from A 2i+2 to D 2i+2 . Next, we set Λ (t) := Λ (t-1) \ {λ (t-1) i } and stack(t) := stack(t -1) -1. This implies that λ (t) j := λ (t-1) j for all j ∈ [0, stack(t)]. Henceforth, we refer to this iteration t as a backtracking iteration for layer 2i. We now move on to the next iteration (t + 1).
Remark: From the above description of the template algorithm, it immediately follows that Invariants 5.8, 5.9, 5.10 and 5.11 continue to hold at the end of each iteration t.
In this section, we analyze the template algorithm, and prove the following lemma.
Lemma 5.12. The algorithm Augment-Template(G, M in , k, γ) runs for at most T = Θ k,γ (1) iterations. It either returns a matching M out in G of size
• n (we say that the algorithm "succeeds" in this case), or it returns Failure. Furthermore, if M in admits a collection of γ • n many node-disjoint length (2k + 1)-augmenting paths in G, then the algorithm succeeds whp.
We start by focusing on bounding the number of iterations (see Corollary 5.14).
Claim 5.13. There can be at most 1/(ψ i ) backtracking iterations for layer 2i, where i ∈ [0, k -1].
Proof. Consider any backtracking iteration t for layer 2i. Then we have σ(t -1) = i, and Invariant 5.10 implies that
Thus, during iteration t, at least ψ i • n nodes at layer (2i + 1) change their status from alive to dead. Since there are at most n nodes at layer (2i + 1), such an event can occur at most 1/(ψ i ) times.
Corollary 5.14. The algorithm Augment-Template(G, M in , k, γ) has at most Θ k,γ (1) iterations.
Proof. Let T f , T b and T 0 respectively denote the total number of forwarding iterations across all layers, the total number of backtracking iterations across all layers, and the total number of iterations across all layers that are neither forwarding nor backtracking.We have T 0 = 1 if the template algorithm returns Failure, and T 0 = 0 otherwise.
We now observe that: there cannot exist a sequence of more than (k + 1) consecutive forwarding iterations, for otherwise, the (k + 2) th forwarding iteration in this sequence would have to take place at a layer ≥ (2k + 2), which does not exist. Hence, we have:
, and the total number of iterations is bounded by:
.
The second inequality follows from Claim 5.13, and the last equality follows from (1).
We now move on to showing that if M in admits a collection γ • n many node-disjoint length (2k + 1)-augmenting paths in G, then the template algorithm succeeds whp. Towards this end, let P denote a maximum-sized collection of node-disjoint length (2k + 1)-augmenting paths in G w.r.t. M in . Let P * ⊆ P be the subset of paths in P that survive the random partitioning. If |P| ≥ γ • n, then Lemma 5.3 guarantees that whp:
(2)
At any point in time during the execution of the algorithm Augment-Template(G, M in , k, γ), we say that a path p ∈ P * is alive if all the nodes on p are alive, and we say that the path p is dead otherwise. Let P * A ⊆ P * and P * D = P * \ P * A respectively denote the set of alive and dead paths at any point in time. Just before the start of iteration 1, we have P * A = P * and P * D = ∅. Subsequently, a path p ∈ P * can change its status from alive to dead only during a backtracking iteration (note that this change occurs in only one direction, i.e., a dead path will never become alive). The next claim upper bounds the number of such changes.
Claim 5.15. During a backtracking iteration for layer 2i, where i ∈ [0, k -1], at most δ i+1 • n many paths in P * moves from P * A to P * D . Proof. Let t ≥ 1 denote a backtracking iteration for layer 2i. During iteration t, the algorithm calls
We have: µ(G ′ ) < δ i+1 • n, for otherwise the call to LargeMatching(., .) would not have returned ⊥.
Just before iteration t, let P ′ ⊆ P * A denote the subset of paths in P * A that pass through some node in C 2i+2 . Only the paths in P ′ move from P * A to P * D at the end of iteration t. We can, however, form a matching in G ′ which contains one edge from each path in P ′ . Hence, we have
This concludes the proof of the claim.
Corollary 5.16. Let ψ = Θ k,γ (1) be a sufficiently small constant depending on k and γ, and suppose that (2) holds. Then throughout the entire duration of the algorithm, we have:
Proof. From (1), Claim 5.13 and Claim 5.15, we infer that:
Now, since we can set ψ to be any sufficiently small constant value depending on k and γ, and since δ 0 ≤ ψ according to (1), from (2) we get:
This concludes the proof.
Corollary 5.17. If (2) holds, then the algorithm does not return Failure.
Proof. For contradiction, suppose that the algorithm returns Failure at the end of an iteration t.
Let i = σ(t -1). Since the algorithm returns Failure after iteration t, we must have i = -1. Furthermore, during iteration t, the call to
Next, observe that C 0 = A 0 . Hence, just before the start of iteration t, we could have formed a matching in G ′ by taking the first edge of each path in P * A . Thus, from Corollary 5.16, we get:
However, both (4) and (5) cannot simultaneously be true. This leads to a contradiction.
Note that if the template algorithm does not return Failure, then it necessarily returns a matching M out of size |M out | ≥ |M in | + ψ k • n (this holds because of Invariant 5.9, Invariant 5.10 and Observation 5.7). Finally, recall that ψ k = Θ k,γ (1) as per (1). Lemma 5.12 now follows from Corollary 5.14, Lemma 5.3 and Corollary 5.17.
In this section, we show how to implement the template algorithm from Section 5.1, when we are allowed access to the input graph G only via adjacency-matrix queries. Throughout this section, we use the following parameters (recall Definition 5.1).
In Section 5.1.1, the template algorithm starts with iteration t = 1. Here, we use the phrase "iteration t = 0" to refer to the scenario just before the start of the first iteration. Towards this end, for consistency of notations, we define ǫ -1 := 2, M (0) := M in , σ(0) :=⊥, stack(0) := -1 and Λ (0) := ∅. Further, we define an oracle alive 0 (v) that is supposed to return Yes if v is alive at the end of iteration 0 (i.e., just before the start of iteration 1), and return No otherwise. The rest of this section is organized as follows. Lemma 5.18 shows how to implement each iteration of the template algorithm, under adjacency-matrix query access to the input graph G. Its proof appears at the end of this section. Theorem 5.2 now follows from Lemma 5.12 and Corollary 5.19.
Lemma 5.18. Suppose that we can access the input graph G only via adjacency-matrix queries, and we have an oracle match M in (.) with Õk,γ (n 1+ǫin ) query time. Then we can implement each iteration t ≥ 0 of the algorithm Augment-Template(G, M in , k, γ), as described in Section 5.1, in Õk,γ (n 2-ǫ t-1 ) time. Furthermore, if the concerned iteration t does not result in the algorithm returning Failure, then we can ensure that we have access to the following data structures at the end of iteration t.
• An oracle match M (t) (.) for the matching M (t) , that has a query time of Õk,γ (n 1+ǫt ).
• An oracle alive t (.) that has a query time of Õk,γ (n 1+ǫt ). When queried with a node v ∈ V , this oracle returns Yes if v is alive at the end of iteration t, and returns No otherwise.
• The values σ(t) and stack(t), and the contents of the set Λ (t) .
Corollary 5.19. Let ǫ out := 9 T • ǫ in , where T = Θ k,γ (1) is the maximum possible number of iterations of the template algorithm (see Lemma 5.12). Then it takes Õk,γ (n 2-ǫin ) time to implement the template algorithm, under adjacency-matrix query access to G. Further, if the template algorithm does not return Failure, then at the end of our implementation we have an oracle match M out (.) for the matching M out returned by it, with query time Õk,γ (n 1+ǫout ).
Proof. By Lemma 5.18, each iteration t of the template algorithm can be implemented in time Õk,γ (n 2-ǫ t-1 ) = Õk,γ (n 2-ǫin ), since ǫ in ≤ ǫ t-1 . Thus, the total time taken to implement the template algorithm is at most Õk,γ (T • n 2-ǫin ) = Õk,γ (n 2-ǫin ).
Suppose that the template algorithm terminates at the end of iteration t, and returns a matching M out . Then, at the end of iteration t of our sublinear implementation, the situation is as follows.
,where σ λ (t) j = 2j for each j ∈ [0, k] (see Invariant 5.8). The sequence of matchings in Λ (t) is nested (see Invariant 5.9). Thus, from this sequence of nested matchings we can extract a set of at least M λ (t) k many node-disjoint length (2k + 1)-augmenting paths w.r.t. M in in G (see Observation 5.7). The template algorithm obtains the matching M out by applying these augmenting paths to M in . In our sublinear implementation of the template algorithm, however, we can access each matching M ∈ Λ (t) only via an oracle match M (.), which has a query time of at most Õk,γ (n 1+ǫt ) (see (6) and Lemma 5.18). Furthermore, we can access the matching M in only via the oracle match M in (.), which also has a query time of at most Õk,γ (n 1+ǫin ) = Õk,γ (n 1+ǫt ).
We now show how to answer a query to the oracle match M out (v). The key observation is this:
M (see the discussion on layered subgraphs in Section 5.1.1). Then the graph G * = (V, E * ) consists of a collection of node-disjoint alternating paths w.r.t. M in . We say that a path in G * is complete iff it has one endpoint at layer 0 and the other endpoint at layer (2k + 1). Now, a node v ∈ V is matched in M out iff: either v ∈ V (M in ), or v / ∈ V (M in ) and v is the starting/end point of a complete path in G * .
Using this observation, we now describe how to answer queries of the form: "Is match M out (v) =⊥ for a given node v ∈ V ?". To answer such a query, we apply the procedure below.
If match M in (v) =⊥, then we return that match M out (v) =⊥. Else if match M in (v) =⊥ and ℓ(v) / ∈ {0, 2k + 1}, then we return that match M out (v) =⊥. Finally, if match M in (v) =⊥ and w.l.o.g. ℓ(v) = 0, then we perform the following steps.
• v 0 ← v.
• For i = 1 to 2k + 1:
-Else if i is even, then v i ← mate M in (v i-1 ).
-If v i =⊥, then return that match M out (v) =⊥.
• Return that match M out (v) =⊥.
It is easy to verify that the above procedure correctly returns whether or not match M out (v) =⊥. We can extend this procedure in a natural manner, which would also allow us to answer the query match M out (v). To summarize, we can answer a query match M out (v) by making at most one call to each of the oracles match M (.), for M ∈ Λ (t) , and at most Θ(k) calls to the oracle match M in (.). Each of these oracle calls take at most Õk,γ (n 1+ǫt ) time, as ǫ t ′ ≤ ǫ t for all t ′ ∈ [1, t]. Since Λ (t) = k, the oracle match M out (.) has a query time of Õk,γ (k • n 1+ǫt ) = Õk,γ (n 1+ǫt ) = Õk,γ (n 1+ǫout ), where the last equality holds since ǫ t ≤ ǫ T = ǫ out . This concludes the proof.
We prove the lemma by induction on t.
Base case (t = 0):
We already have the oracle match M (0) (.) with query time Õk,γ (n 1+ǫ 0 ), since ǫ 0 = ǫ in and M (0) = M in . We set σ(t) ←⊥, stack(t) ← -1 and Λ (0) ← ∅. We now claim that we already have the oracle alive 0 (.). This is because a node v ∈ V is alive just before the start of iteration 1 if and only if v ∈ V H . Furthermore, given a query alive 0 (v), we can determine whether v is in V H by checking the value of ℓ(v), setting u ← mate M (0) (v), and then checking the value of ℓ(u) if u =⊥. Thus, answering a query to the oracle alive 0 (.) takes Õk,γ (n 1+ǫ 0 ) time. So, we can implement iteration 0 in O(1) time, and Lemma 5.18 holds for t = 0.
We assume that Lemma 5.18 holds for all t ′ ∈ [0, t-1], and that we have access to the data structures constructed during all these past iterations. We now focus on implementing the current iteration t (see Section 5.1.1) under adjacency-matrix query access to G. Let i = stack(t -1). If i = k, then the algorithm would terminate after iteration (t -1). Henceforth, we assume that i ∈ [-1, k -1].
In the current iteration t, the template algorithm wants to first compute a matching M (t) by calling the subroutine LargeMatching(C 2i+2 ∪ A 2i+3 , δ i+1 ). We first show that we can efficiently query whether or not a given node in V belongs to the set C 2i+2 ∪ A 2i+3 . Subsequently, we split up our implementation of iteration t into two steps, as described below.
Claim 5.20. Given any node v ∈ V , we can determine if v ∈ C 2i+2 in Õk,γ (n 1+ǫ t-1 ) time.
Proof. We first check the value of ℓ(v) and call alive t-1 (v). Now, we consider the following cases.
(i) ℓ(v) = 2i + 2. Here, we return that v / ∈ C 2i+2 .
(ii) ℓ(v) = 2i + 2 and alive t-1 (v) = No. Here, we also return that v / ∈ C 2i+2 .
(iii) ℓ(v) = 2i + 2, alive t-1 (v) = Yes, and i = -1. Here, we return that v ∈ C 2i+2 .
(iv) ℓ(v) = 2i + 2, alive t-1 (v) = Yes and i ≥ 0. Here, we first set u v ← mate M in (v), which takes Õk,γ (n 1+ǫin ) = Õk,γ (n 1+ǫ t-1 ) time. Next, we call match M λ (t-1) i (u v ), which also takes at most Õk,γ (n 1+ǫ t-1 ) time. Finally, we return that v ∈ C 2i+2 iff match
The correctness of the above procedure follows from the definition of the set C 2i+2 . Furthermore, the preceding discussion implies that this procedure overall takes at most Õk,γ (n 1+ǫ t-1 ) time.
Corollary 5.21. Given any v ∈ V , we can determine if v ∈ C 2i+2 ∪ A 2i+3 in Õk,γ (n 1+ǫ t-1 ) time.
Proof. We can determine if v ∈ A 2i+3 by checking the value of ℓ(v) and making a query alive t-1 (v), which takes Õk,γ (n 1+ǫ t-1 ) time. The corollary now follows from Claim 5.20.
Step I: Constructing the oracle match M (t) (.). Armed with Corollary 5.21, we mimic the call to LargeMatching(C 2i+2 ∪ A 2i+3 , δ i+1 ) in the template algorithm, by invoking Theorem 4.1 with
1 and t A = Õk,γ (n 1+ǫ t-1 ). 10 If Theorem 4.1 returns ⊥, then we set M (t) := ∅, and the trivial oracle match M (t) (.) has O(1) = Õk,γ (n 1+ǫt ) query time. Otherwise, Theorem 4.1 returns an oracle match M (.) for a matching M , and we set M (t) := M . By (6) and Theorem 4.1, this oracle match M (t) (.) has query time:
Finally, from (6) and Theorem 4.1, we infer that overall Step I takes time:
In the above derivation, the second equality holds since ǫ = 2ǫ t-1 ≤ 9 T ǫ in ≤ 1/5 (see (6) and Definition 5.1), whereas the third equality holds since t A = Õk,γ (n 1+ǫ t-1 ).
Step II: Determining σ(t), stack(t), Λ (t) , and the oracle alive (t) (.). We set σ(t) ← 2i + 2.
We now fork into one of the following three cases.
Step I, the invocation of Theorem 4.1 returned an oracle match M (.) for a matching M , and we set M (t) := M . This will be referred to as a forwarding iteration at layer 2i + 2. In this case, we set Λ (t) ← Λ (t-1) ∪ {t} and stack(t) ← stack(t -1) + 1. Now, we observe that the set of alive nodes does not change during such a forwarding iteration, and so we already have the oracle alive t (.), because alive t (v) = alive (t-1) (v) for all v ∈ V . Accordingly, the oracle alive t (.) has query time Õk,γ (n 1+ǫ t-1 ) = Õk,γ (n 1+ǫt ).
Step I, the invocation of Theorem 4.1 returned ⊥, and i = -1. Here, the algorithm terminates and returns Failure.
Case (c): In Step I, the invocation of Theorem 4.1 returned ⊥, and i ≥ 0. This will be referred to as a backtracking iteration at layer 2i. In this case, we set Λ (t) ← Λ (t-1) \ {λ (t-1) i } and stack(t) ← stack(t -1) -1. Now, we observe that due to iteration t, only the nodes in C 2i+2 and their matched neighbors under M in (who are at layer 2i + 1), change their status from alive to dead. The status of every other node remains unchanged. Thus, we can answer a query alive t (v), in Õk,γ (n 1+ǫt ) time, as follows.
We first check the value of ℓ(v), query alive t-1 (v) and match M in (v), and determine whether or not v ∈ C 2i+2 by invoking Claim 5.20. Overall, this takes Õk,γ (n 1+ǫ t-1 ) + Õk,γ (n 1+ǫin ) = Õk,γ (n 1+ǫt ) time. Next, we consider three cases.
(i) ℓ(v) / ∈ {2i + 1, 2i + 2}. Here, we return alive t (v) = alive (t-1) (v).
(ii) ℓ(v) = 2i + 2. Here, if v ∈ C 2i+2 then we return alive t (v) = No; otherwise we return alive t (v) = alive t-1 (v). (iii) ℓ(v) = 2i + 1. Here, we set u v ← mate M in (v). Now, if u v ∈ C 2i+2 then we return alive t (v) = No; otherwise we return alive t (v) = alive t-1 (v).
To summarize, Step I takes Õk,γ (n 2-ǫ t-1 ) time, whereas Step II takes only O(k) = O k,γ (1) time. Furthermore, at the end of Step II we have all the desired data structures for iteration t, and both the oracles match M (t) (.) and alive t (.) have a query time of at most Õ(n 1+ǫt ). Finally, Theorem 4.1 ensures that whp, the way we decide whether we are in case (a), case (b) or case (c) is consistent with the choice made by the template algorithm in the same scenario (see the discussion on "implementing iteration t" in Section 5.1.1, and how the subroutine LargeMatching(S, δ) is defined in the second paragraph of Section 5.1). This concludes the proof of Lemma 5.18.
In this section, starting from an empty matching, we repeatedly apply Theorem 5.2 to obtain our main results in the sublinear setting. They are summarized in the theorem and the corollary below, which are restatements of Theorem 1.3. Theorem 6.1. Let γ, ǫ ′′ ∈ (0, 1) be any two small constants, and let G be the input graph with n nodes which we can access via adjacency-matrix queries. Then for a sufficiently small constant ǫ ′ ∈ (0, ǫ ′′ ), there exists an algorithm which: In Õγ (n 2-ǫ ′ ) time, returns an oracle match M (.) for a (1, 3γn)-approximate matching M in G, where the oracle match M (.) has Õγ (n 1+ǫ ′′ ) query time.
Corollary 6.2. Given adjacency-matrix query access to an n-node graph G and any constant γ ∈ (0, 1), in Õγ (n 2-ǫ ) time we can return a (1, 4γn)-approximation to the value of µ(G), whp. Here, ǫ ∈ (0, 1) is a sufficiently small constant depending on γ.
Proof. First, we apply Theorem 6.1, with ǫ = ǫ ′ , to get the oracle match M (.) in Õγ (n 2-ǫ ) time. Note that M is a (1, 3γn)-approximate matching in G = (V, E). Using Chernoff bound, we now compute a (1, γn)-approximate estimate μ of |M | by sampling, uniformly at random, a set S of Õγ (1) nodes from V and querying match M (v) for each node v ∈ S. This takes Õγ (n 1+ǫ ′′ ) = Õγ (n 2-ǫ ) time. The last inequality holds since ǫ = ǫ ′ and ǫ ′′ are chosen to be sufficiently small, so that 1 + ǫ ′′ ≤ 2ǫ. It is now easy to observe that μ is a (1, 4γn)-approximation to the value of µ(G).
Algorithm 4 contains the relevant pseudocode. We slightly abuse the notation in step 2-(b) of Algorithm 4, when we write Z = (M out , ǫ out ). Here, we essentially mean that Augment(G, M in , i, γ 2 , ǫ in ) returns the oracle match M out (.) with query time Õγ (n 1+ǫout ). Similarly, in step 2-(b), when we write M in ← M out , this means that henceforth we will refer to the oracle match M out (.) as match M in (.).
The idea behind Algorithm 4 is simple and intuitive. We start by initializing M in ← ∅, k ← ⌈1/γ⌉ and ǫ in ← ǫ ′ , where ǫ ′ ∈ (0, 1) is a sufficiently small constant. At this point, we trivially have the oracle match M in (.) with query time Õγ (n 1+ǫin ). The algorithm now runs in rounds. In each round, it repeatedly tries to augment the matching M in along small-length augmenting paths, by successively calling Augment(G, M in , i, γ 2 , ǫ in ) for i ∈ [0, k]. Whenever a call to Augment(•) succeeds, the algorithm feeds its output into the next call to Augment(•). The algorithm terminates whenever it encounters a round where every call to Augment(•) returns Failure. Claim 6.3. Algorithm 4 runs for Õγ (1) rounds, and makes Õγ (1) calls to Augment(•).
Proof. Say that a given round of Algorithm 4 is successful iff during that round: for some i ∈ [0, k], the call to Augment(G, M in , i, γ 2 , ǫ in ) succeeded (see Theorem 5.2 and step 2-(a) of Algorithm 4). By Theorem 5.2, each time a call to Augment(G, M in , i, γ 2 , ǫ in ) succeeds, it increases the size of the matching M in (see step 2-(b) of Algorithm 4) by at least Θ γ (1) • n. Since µ(G) ≤ n, such an event can occur at most Θ γ (1) times. Finally, each round of Algorithm 4 consists of (k + 1) = Θ γ (1) calls to Augment(•), and all but the last round is successful. This implies the claim.
Algorithm 4 Near-optimal-matching-oracle (G = (V, E), γ). Choose ǫ ′ ∈ (0, 1) to be a sufficiently small constant.
2. For i = 0 to k:
Return the oracle match M (•), which has query time Õγ (n 1+ǫ ′′ ).
Claim 6.4. Suppose that at the start of a given round of Algorithm 4, there exists a collection of at least γ 2 • n many node-disjoint length (2i + 1)-augmenting paths w.r.t. M in in G, for some i ∈ [0, k].
Then whp, Algorithm 4 does not terminate at the end of the given round.
Proof. If there exists some j ∈ [0, i -1] such that the call to Augment(G, M in , j, γ 2 , ǫ in ) succeeds during the given round, then it immediately implies the claim (since we would have τ = True when the round ends and so the While loop in Algorithm 4 will run for at least one more iteration).
For the rest of the proof assume that during the given round, for all j ∈ [0, i -1] the call to Augment(G, M in , j, γ 2 , ǫ in ) returns Failure, and hence the matching M in does not change during iterations j = 0 to i -1 of the For loop. Accordingly, at the start of the concerned iteration i of the For loop, the matching M in still admits a collection of at least γ 2 • n many node-disjoint length (2i + 1)-augmenting paths in G. Thus, by Theorem 5.2, the call to Augment(G, M in , i, γ 2 , ǫ inp ) succeeds whp. So, it follows that Algorithm 4 does not end after the given round, whp. Corollary 6.5. When Algorithm 4 terminates, whp M in is a (1, 3γn)-approximate matching in G.
Proof. Let M * be a maximum matching in G. By Claims 6.3 and 6.4, the following holds whp when the algorithm terminates: For all i ∈ [0, k], there exists at most γ 2 • n many length-(2i + 1) augmenting paths in M in ∪ M * .
As k = ⌈1/γ⌉, the augmenting paths in M in ∪ M * that are of length ≤ 2k + 1 contribute at most (k + 1) • γ 2 n ≤ 2γn extra edges to M * compared to M in . On the other hand, augmenting paths
Since Algorithm 4 makes only constantly many calls to Augment(•), we can choose ǫ ′ > 0 to be sufficiently small so as to guarantee that 0 < ǫ ′′ ≪ 1 (see Claim 6.3 and Theorem 5.2). Further, during the execution of Algorithm 4, each call to Augment(•) takes Õγ (n 2-ǫin ) = Õγ (n 2-ǫ ′ ) time. Theorem 6.1 now follows from Claim 6.3 and Corollary 6.5. matching M of G, which takes O ǫ (m init ) time [DP14]. Define µ * = |M |. Throughout the phase, µ * continues to remain a (1 + 2ǫ)-approximate estimate of µ(G), and we continue to output the same value µ * . This leads to an amortized update time of:
The last equality holds since |E| = m = Θ(m init ) throughout the phase. We can ensure that throughout the phase, the algorithm explicitly maintains M , which remains a (1 + 2ǫ)-approximate maximum matching of G. This gives us the matching oracle match M (.), with constant query time.
Type-II Phase: At the start of a type-II phase, we have μ < |E| 0.5+ǫ 0 . Let μinit and m init respectively denote the value of μ and |E| at the start of the phase. The phase will last for the next ǫμ init updates. Hence, µ(G) can change by at most a multiplicative (1 + ǫ) factor during the phase.
At the start of the phase, for each i ∈ I, we find a (1, 4γ)-approximate estimate µ * i of µ(G φ i ). We obtain µ * i by invoking Corollary 6.2 on G φ i , with γ = ǫ 2 .foot_7 This takes time:
where ǫ * ∈ (0, 1) is a sufficiently small constant depending on ǫ. Since |I| = Õ(1), overall we spend Õǫ (μ init ) 2-ǫ * time to compute µ * i for all i ∈ I. Next, in |I| = Õ(1) time, we find an index j ∈ I which maximizes the value µ * j . From Theorem 7.2, it follows that:
As γ = ǫ 2 , we infer that µ * j is a purely multiplicative (1 + Θ(ǫ))-approximate estimate of µ(G). We continue to output the same value µ * j throughout the phase, since we have already observed that during the phase µ(G) changes by at most a multiplicative (1 + ǫ) factor.
The phase lasts for ǫμ init updates. Accordingly, this leads to an amortized update time of:
Õǫ (μ init ) 2-ǫ * ǫμ init = Õǫ (μ init ) 1-ǫ * = Õǫ (m init ) 0.5+ǫ 0 -ǫ * = m 0.5-Ωǫ(1) .
The last equality holds because we can ensure that ǫ 0 is sufficiently small compared to ǫ * (which, in turn, depends on ǫ), and since |E| = m = Θ(m init ) throughout the duration of the phase. Because of (7), at the start of the phase we can construct the oracle match M (.) by invoking Theorem 6.1 on the graph G φ j * . Over the ǫμ init edge updates of the phase, M continues to remain a (1 + O(ǫ))-approximate maximum matching in G. Finally, to maintain the oracle under edge insertions/deletions during the phase, we simply ignore edge deletions and assume that if a vertex is matched by a deleted edge of M then it is unmatched.
Improving the update time bound to worst-case: Recall that μinit denotes the value of μ at the beginning of a phase. As observed after the initialization of a phase the output maintained by the algorithm remains (1 + O(ǫ))-approximate for the next O(ǫ • μinit ) updates. Furthermore, the total computational work done by the algorithm in both types of phases is upper bounded by Õ(μ 2-ǫ * init ) for some small constant ǫ * ∈ (0, 1) depending on the parameters of the algorithm. Let G i stand for the state of the input graph at the beginning of phase i and let A(G i ) stand for the output of the previously described algorithm initialized on G i . Let μinit,i stand for the value of μinit at the beginning of phase i. We will now describe the behaviour of the worst-case update time algorithm.
The improved algorithm similarly initializes it's output to be A(G 1 ). Throughout the first three phases it does not alter it's output and during the first two phases it doesn't complete any background computation. During phase i for i > 2 the algorithm calculates A(G i-2 ) distributing the work evenly throughout the phase. Note that by phase i the algorithm has complete knowledge of G i-2 . At the end of the same phase it switches it's output to be A(G i-2 ).
As the algorithm only outputs a matching size estimate and an oracle and not an actual matching this switch is done in constant time. Computing A(G i-2 ) takes time proportional to Õ(μ 2-ǫ * init,i-2 ) and is distributed over ǫ • μinit,i updates. As during a phase µ(G) may change by at most a 1 + O(ǫ) multiplicative factor we must have that μinit,i = Θ(μ init,i-2 ). The amortized implementation amortizes the work of computing A(G i-2 ) over ǫ • μinit,i-2 updates. This implies that the worstcase update time guarantee of the delayed rebuild based algorithm matches the amortized versions update time within a constant factor.
Basic Properties of Randomized Greedy Matching. Recall that d is the given parameter where d ≥ d. We set the threshold ℓ = Θ(d log(n)/ǫ) such that ℓ ≥ α • 8 ǫ . We have by Markov's inequality that Pr 8). We also say that π ∈ Π is good if f (π) ≤ ǫ, otherwise we say that it is bad.
Algorithm 7 TestPerm(π)
1. Sample r = 1000 log(n)/ǫ vertices independently: v 1 , . . . , v r .
2. Let X = |i | {T (v i , π) > ℓ}| and f = X/r.
3. If f ≤ 3 4 ǫ, return "yes". Otherwise, return "no".
A simple procedure in Algorithm 7 accepts a great permutation and rejects a bad permutation with high probability.
Lemma A.3. If π is great, then TestPerm(π) returns "yes" with high probability. If π is bad, then TestPerm(π) returns "no" with high probability.
Proof. If π is great but TestPerm(π) returns "no", then we have f (π) ≤ ǫ/2 but f > 3ǫ/4. Since Preprocessing. The preprocessing algorithm is as follows. First, independently sample O(log n) random edge-permutations π 1 , . . . , π O(log n) . For any i, if TestPerm(π i ) returns "yes", then set π * ← π i .
Observe that this argument holds regardless of the choice of M * the statement remains true as G undergoes updates even when the updates are made by an adaptive adversary. The contractions φ i j are fixed at initialization. The task of the algorithm is to maintain maximum matching size estimate μ(G) and hence maintain the accurate guess of µ(G) and to update the contracted graphs. Each contracted graph may undergoes a single update per update to G and there are Õ(1) contracted graphs. All parts included the worst-case update time of the algorithm is Õ(1). implying that M is always a (1 + O(ǫ))-approximate matching.
To see why µ(G) ≥ m/2n, consider the process where we repeatedly choose an edge e and delete both endpoints of e from the graph until no edge is left. Since the set of deleted edges forms a matching, we may repeat at most µ(G) times. Also, each deletion removes at most 2∆ edges from the graph. Therefore, m ≤ µ(G) • 2∆ ≤ µ(G) • 2n.
Adjacency List Adjacency Matrix Guarantee Approx Time Approx Time Approx Time [PR07] (2, ǫn) ∆ O(log(∆/ǫ))
[NO08]
(2, ǫn) 2 O(∆) /ǫ 2 (1, ǫn)
(2, ǫn)
(2, ǫn)
(2, ǫn)
(1.5, ǫn) nd 1-Ω(ǫ 2 ) 1.5 + ǫ n∆ 1-Ω(ǫ 2 ) (1.5, ǫn) n 2-Ω(ǫ 2 )
[BRR23] bipartite graph only
(1.5 -Ω(1), o(n)) n 2-Ω(1) 1.5 -Ω(1) n 2-Ω(1) (1.5 -Ω(1), o(n)) n 2-Ω(1)
(1, ǫn) n 2-Ωǫ(1)
Table 1: Summary of sublinear-time algorithms for estimating the size of maximum matching. We omit polylog(n/ǫ) factors. ∆ and d denote the maximum and average degree of the graph, respectively.
In[RSW22], they use different notation and write 0.99-approximation instead of 1.01.
[BRR23] also announced a Ω(n 1.2 )-time lower bound for (3/2 -Ω(1), o(n))-approximation.
The dynamic (3/2 -Ω(1))-approximate algorithm in[Beh23] does not have explicit relationship to streaming algorithms. It is obtained using sublinear algorithms to improve the (3/2)-approximation guarantee of the tight instances of EDCS.
Think of a n×n bipartite graph which consists only of a perfect matching. Using o(n 2 ) adjacency-matrix queries, it is not possible to out Ω(n) matching edges in this input instance. The lower bound can be extended even if we allow adjacency-list queries by adding ǫn dummy vertices, each of which connects to every other vertex.
Note that Hoeffding bound Proposition 3.1 is not strong enough here.
In fact, if we define M2 as M i from Line 2g in Algorithm 1, we would even have that |M2| ≥ 4δinn w.h.p. But we did use this bound just to avoid white-boxing the preprocessing algorithm and make the presentation of the query algorithm more modular.
The reader should keep in mind that in the current section (Section 6), we are using the symbol A to denote the set of alive nodes across all the layers. This is different from the way the symbol A is being used in the statement of Theorem 4.1, where it refers to any arbitrary subset of nodes.
It is trivial to verify that Corollary 6.2 holds even when applied on a multigraph.