A $0.51$-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time

In order to be able to use two levels of recursive oracle calls, we need to sparsify the graph. We first sample $\tilde{O}(n\sqrt{n})$ edges and construct a maximal matching on the sampled edges to sparsify the induced subgraph of unmatched vertices. This sparsification step is formalized in Algorithm 2. In Lemma 6, we show that if we sample enough edges, then vertices that remain unmatched after this phase have an induced degree of $\sqrt{n}$. This step is very similar to the algorithm of [13] for approximating a maximal matching.

For each vertex $v$ in the graph, the algorithm samples $\tilde{O}(\sqrt{n})$ vertices from the adjacency list of the vertex $v$ if it is not matched by the time the algorithm processes the vertex in Line 3. Thus, the total running time is at most $\tilde{O}(n\sqrt{n})$. $\mathrm{⊲}$

We will show that for every $v\in V$, the probability that $v\in V\setminus V(M)$ and the degree of $v$ in $G[V\setminus V(M)]$ is larger than $\sqrt{n}$ is at most $1/n^2$. The lemma then follows by a union bound over all $v\in V$.

Consider the moment before $v$ is processed. Assume that at this time, still $v\in V\setminus V(M)$ and the degree of $v$ in $G[V\setminus V(M)]$ is larger than $\sqrt{n}$. Then, each of the $c$ samples has a probability of at least $\sqrt{n}/n$ to be one of the unmatched neighbors, in which case $v$ will become matched. Thus the probability that $v$ remains unmatched after it is processed is at most

$◀$

Now we are ready to present our sublinear algorithm. After sparsifying the graph by finding a partially maximal matching $M$, we try to augment $M$ in two different ways that we have outlined in Section 2 and which are formalized in Algorithm 3. See also Figure 1.

For simplicity, we pretend that $kb\in \mathbb{Z}$ throughout the paper. Since $k$ is an arbitrarily large constant, using $kb$ instead of $\lceil kb\rceil$ leads to an arbitrarily small error in the calculations. We also note that a maximal $b$-matching can be viewed as maximal matching if we duplicate vertices multiple times.

First, we try to augment the matching by designing a maximal matching oracle for $G[V\setminus V(M)]$ vertices and then another oracle for finding a $b$-matching between the vertices newly matched using the new oracle and unmatched vertices. Let $M^{\prime }$ be the maximal matching of $G[V\setminus V(M)]$ that can be obtained by the oracle. We try to augment it with a $b$-matching $B_1$.

However, it is also possible that $|M^{\prime }|$ is small compared to $|M|$, which implies that in the previous case, the $b$-matching does not help to find many augmenting paths, as the size of the maximal matching that we try to augment is too small. To account for this case, the algorithm also finds a $b$-matching $B_2$ between $V(M)$ and $V\setminus V(M)$.

Note that because the algorithm finds the initial matching $M$ explicitly, checking whether a vertex belongs to $V(M)$ or not can be done in $O(1)$ time.

There are some technical details in the implementation of the algorithm that are not included in the pseudocode:

• $\mathrm{■}$

  Access to the adjacency list of an induced subgraph: Both in Algorithm 4 and Algorithm 5, we run the algorithm of Proposition 3 for some induced subgraph of $G$ (for example, line 5 of Algorithm 5). However, Proposition 3 works with access to the adjacency list of the input graph. To address this issue, we leverage an important property of the algorithm in Proposition 3, namely that it only needs to find a random neighbor of a given vertex at each step of its execution. Now, whenever the algorithm requires a random neighbor of vertex $v$ in a subgraph $H$, it queries random neighbors in the original graph $G$ until it finds one that belongs to $H$. This increases the running time of the algorithm, as it may take $\omega (1)$ time to locate a valid neighbor in $H$, which we will formally bound in our runtime analysis.

• $\mathrm{■}$

  Nested oracles in line 8 of Algorithm 4: Unlike $M$, we do not explicitly construct the maximal matching $M^{\prime }$ in Algorithm 4. Moreover, the edges of the subgraph $G_1^{\prime }$ connect vertices matched by $M^{\prime }$ with those that remain unmatched in either $M$ or $M^{\prime }$. Hence, to verify whether an edge belongs to $G_1^{\prime }$, we need to determine whether its endpoints are matched or unmatched in $M^{\prime }$ by accessing the algorithm of Proposition 3. This again increases the algorithm’s runtime, which we will also formally bound in our runtime analysis.

Since $G$ is bipartite, by integrality of the bipartite matching polytope, it is enough to exhibit a fractional matching $x$ of the appropriate value ${\sum }_e{x}_e$. For case 1, we set

Note that $M$, $M^{\prime }$ and $B_1$ are pairwise disjoint, and $B_1$ has no edge to $V(M)$. Therefore it is easy to verify that the degree constraints for $x$ are satisfied. For case 2, we similarly set

$◀$

The following lemma states the $(2-\sqrt{2})$-approximation guarantee of the “maximal matching plus $b$-matching” approach obtained in prior work, for both bipartite and general graphs. We will invoke it for appropriate subgraphs of $G$ to obtain our guarantee.

The first statement is the same as Lemma 4, and shown as Lemma 3.3 in [12]. The second statement is shown as Claim 5.5 in [2]. $◀$

The following lemma is the crux of our approximation ratio analysis.

Fix a maximum matching $M^{\ast }$ in $G$, and partition its edges as follows (see Figure 2):

• $\mathrm{■}$

  $M_2^{\ast }$ are those with both endpoints in $V(M)$,

• $\mathrm{■}$

  $M_2^{{}_{}{}^{\prime }\ast }$ are those with one endpoint in $V(M)$ and the other in $V(M^{\prime })$,

• $\mathrm{■}$

  $M_2^{{}_{}{}^{\prime \prime }\ast }$ are those with both endpoints in $V(M^{\prime })$,

• $\mathrm{■}$

  $M_1^{\ast }$ are those with one endpoint in $V(M)$ and the other in $V\setminus V(M)\setminus V(M^{\prime })$,

• $\mathrm{■}$

  $M_1^{{}_{}{}^{\prime }\ast }$ are those with one endpoint in $V(M^{\prime })$ and the other in $V\setminus V(M)\setminus V(M^{\prime })$.

Since $M\cup M^{\prime }$ is maximal, $M^{\ast }$ cannot have edges with no endpoints in $V(M)\cup V(M^{\prime })$. We thus have

Also, by maximality of $M^{\ast }$ and simple counting,

We will use Lemma 8 to analyze both cases in Algorithm 3. For case 1, we can use $G^{\prime }=G[V\setminus V(M)]$; in this graph, $M^{\prime }$ is a maximal matching, and $B_1$ is a $b$-matching as in the statement of Lemma 8 (see Figure 2), thus we have

since $M_1^{{}_{}{}^{\prime }\ast }\cup M_2^{{}_{}{}^{\prime \prime }\ast }$ is a matching in $G^{\prime }=G[V\setminus V(M)]$. With Equation 2 this gives

For case 2, we can instead use $G^{\prime }=G[V(M)]\cup G[V(M),V\setminus V(M)]$; in this graph, $M$ is a maximal matching, and $B_2$ is a $b$-matching as in the statement of Lemma 8 (see Figure 2), thus

since $M_2^{\ast }\cup M_2^{{}_{}{}^{\prime }\ast }\cup M_1^{\ast }$ is a matching in $G^{\prime }$. Using Equations 3 and 4, we can bound the left-hand side of this lemma’s statement as

We bound the maximum by a weighted average with weights $\beta$ and $1-\beta$ for some $\beta \in [0,1]$ to be determined ($\max (x,y)\ge \beta x+(1-\beta )y$):

We want $(\ast )$ to hold for some $\gamma$ (the approximation ratio) as large as possible. For $(\ast )$ to hold, we need to satisfy:

By solving for $\frac{\beta }{2}+(2-\sqrt{2})(1-\beta )=(2-\sqrt{2})\beta$ we get $\beta =\frac{12+2\sqrt{2}}{17}$ and $\gamma =\frac{4(5-2\sqrt{2})}{17}-O(\epsilon )>0.5109$. $◀$

The proof of Lemma 10 is routine. We defer it to the full version of the paper.

Without loss of generality, we assume that $|V\setminus V(M)|=\mathrm{\Omega }(n)$; otherwise, Algorithm 3 does not need to execute Algorithm 4, as the estimate from Algorithm 5 suffices.

The proof consists of two parts: first we show that line 6 of the algorithm can be implemented in $\tilde{O}(\overline{d}(G))$ expected time, and then we prove that line 8 of the algorithm can be implemented in $\tilde{O}(\overline{d}(G)\cdot \sqrt{n})$ expected time.

For the first part, let $G^{\prime \prime }=G[V\setminus V(M)]$ and let $v$ be a vertex in $G^{\prime \prime }$. In the adjacency list of $v$ in the original graph, which contains ${\mathrm{deg}}_G(v)$ elements, only ${\mathrm{deg}}_{G^{\prime \prime }}(v)$ of them are neighbors in $G^{\prime \prime }$. Thus, to find a neighbor in $G^{\prime \prime }$, we need to randomly sample $T(v)={\mathrm{deg}}_G(v)/{\mathrm{deg}}_{G^{\prime \prime }}(v)$ elements from $v$’s adjacency list in expectation. Consequently, using Proposition 12, the expected time required to execute the random greedy maximal matching oracle for a randomly chosen vertex and permutation in $G^{\prime \prime }$ is

Note that this bound is for $r$ random permutations and vertices. However, in the algorithm, we only choose one permutation $\pi$ and then run the random greedy maximal matching for $r$ randomly chosen vertices. Let $S$ be the set of $r$ vertices that are chosen uniformly at random. Also, let $F(v,\pi )$ be the running time of random greedy maximal matching on vertex $v$ and permutation $\pi$. Therefore, the expected running time can be written as

Since $r=\tilde{O}(1)$, the expected running time of the first part is $\tilde{O}(\overline{d}(G))$.

We prove the second part in a few steps. As a first step, for simplicity, assume that we have access to the adjacency list of $G_1^{\prime }$ and there is no need to run nested oracles. Then, using Proposition 3, the expected running time of line 8 is bounded by $\tilde{O}(\overline{d}(G_1^{\prime }))$ for $r=\tilde{O}(1)$ random permutations and random vertices.

Now, suppose that we have access to the adjacency list of $G^{\prime \prime }=G[V\setminus V(M)]$ instead of $G_1^{\prime }$. By Proposition 12, the total expected runtime of the outer ($b$-matching) oracle is

where $T_{\mathrm{outer}}(v)$ is the expected time needed to find a random neighbor of $v$ in $G_1^{\prime }$. To find such a neighbor, we sample neighbors $w$ of $v$ in $G^{\prime \prime }$ and check whether $w$ is matched in $M^{\prime }$ using the inner oracle. The expected number of these checks until a vertex $w$ with $(v,w)\in E(G_1^{\prime })$ is found is $\tilde{O}({\mathrm{deg}}_{G^{\prime \prime }}(v)/{\mathrm{deg}}_{G_1^{\prime }}(v))$. The expected cost of each check is ${\text{E}}_{w:(v,w)\in E(G^{\prime \prime })}[{\mathrm{cost}}_{\mathrm{inner}}(w)]$, where ${\mathrm{cost}}_{\mathrm{inner}}(w)$ is the runtime of invoking the inner oracle to check if $w$ is matched in $M^{\prime }$. Putting this together, the expected total runtime is

where $T_{\mathrm{inner}}(v)$ is the expected time needed to find a random neighbor of $v$ in $G^{\prime \prime }$. Under our assumption of having access to the adjacency list of $G^{\prime \prime }$, $T_{\mathrm{inner}}(v)=O(1)$ and thus we can finish bounding with $\tilde{O}(\sqrt{n}\cdot \overline{d}(G^{\prime \prime }))=\tilde{O}(\sqrt{n}\cdot \overline{d}(G))$.

Now we lift the assumption of having access to the adjacency list of $G^{\prime \prime }$. This means that, similarly as in the first part, we need to sample $T_{\mathrm{inner}}(v)={\mathrm{deg}}_G(v)/{\mathrm{deg}}_{G^{\prime \prime }}(v)$ vertices from the adjacency list of $v$ in expectation (checking if a vertex is matched in $M$ is done in $O(1)$ time). Then the total bound becomes

Also $T_{\mathrm{outer}}(v)$ increases by ${\mathrm{deg}}_G(v)/{\mathrm{deg}}_{G_1^{\prime }}(v)$, which increases the total runtime only by

Finally, since we have a fixed permutation $\pi$ instead of $r$ random permutations, we can use the exact same argument as in the proof of the first part to conclude the proof. $◀$

It is enough to show that it takes $\tilde{O}(\overline{d}(G))$ time to run the algorithm of Proposition 3 (the $b$-matching oracle) for each sampled vertex and permutation, as we have $r=\tilde{O}(1)$. We repeat the same arguments as in the proof of Lemma 13.

Let $v$ be a vertex in the graph $G_2^{\prime }=G[V(M),V\setminus V(M)]$. Note that in the adjacency list of $v$ in the original graph, which contains ${\mathrm{deg}}_G(v)$ elements, only ${\mathrm{deg}}_{G_2^{\prime }}(v)$ of the elements are neighbors in $G_2^{\prime }$. Thus, we need to randomly sample $T(v)={\mathrm{deg}}_G(v)/{\mathrm{deg}}_{G_2^{\prime }}(v)$ elements of the adjacency list of $v$ to find a neighbor in $G_2^{\prime }$. Recall that we can check whether a vertex is matched in $M$ in $O(1)$ time. Therefore, using Proposition 12, the expected time needed to run the random greedy maximal matching for a random vertex and permutation in $G_2^{\prime }$ is

$◀$

By Claim 5, the sparsification step takes $\tilde{O}(n\sqrt{n})$ time. Also, by Lemmas 13 and 14, Algorithms 4 and 5 run in $\tilde{O}(\overline{d}(G)\cdot \sqrt{n})$ and $\tilde{O}(\overline{d}(G))$ expected time, respectively. To establish a high probability bound on the time complexity, we execute $O(\log n)$ instances of the algorithm in parallel and halt as soon as the first one completes. By applying Markov’s inequality, we deduce that each individual instance terminates within $\tilde{O}(n\sqrt{n})$ time with constant probability. As a result, with high probability, at least one of these instances finishes within $\tilde{O}(n\sqrt{n})$ time. This concludes the proof. $◀$

Now we are ready to prove the final theorem of this section.

By Lemma 10, Algorithm 3 achieves multiplicative-additive approximation of $(0.5109,o(n))$. Moreover, the running time of Algorithm 3 is $\tilde{O}(n\sqrt{n})$ with high probability by Lemma 15. $◀$