Matching is as Easy as the Decision Problem, in the NC Model

Introduction

Is matching in NC, i.e., is there a deterministic fast parallel That runs in polylogarithmic time using polynomially many processors. algorithm for finding a perfect or, more generally, a maximum matching in a general graph? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms [KUW85, MVV87]. Over the last five years, the TCS community has launched a relentless attack on this question, leading to the discovery of numerous powerful ideas [FGT16, ST17, GG15, AV20, San18]. We give what appears to be the culmination We note that since the appearance of this paper in aXiv, in January 2019, we are not aware of any new development on the ”Is matching in NC?” question, in contrast to the frenzied activity over the prior years. of this line of work: An NC algorithm for finding a minimum weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle, say ${\mathcal{O}}$, for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem. Henceforth, by small weights we will mean polynomially bounded edge weights and acronym MWPM will be short for minimum weight perfect matching.

The difficulty of obtaining an NC matching algorithm led researchers to study matching vis-a-vis certain clever relaxations of the class NC. One such relaxation is pseudo-deterministic RNC. This is an RNC algorithm with the additional property that on the same graph, it must return the same (i.e., unique) solution for almost all choices of random bits [GG11, GG15]. Recently, [GG15] gave such an algorithm for perfect matching in bipartite graphs. A second relaxation of NC is quasi-NC, under which the algorithm must run in polylogarithmic time, though it can use $O(n^{\log^{O(1)}n})$ processors; see Section 1.1 for results obtained for this model.

A corollary of our result extends [GG15] to general graphs as follows: The precise decision problem for our result is: Given a graph $G$ with small weights and a number $W$, is there a perfect matching of weight at most $W$ in $G$. Since binary search over $W$ will take $O(\log n)$ iterations, this is NC equivalent to: Find the weight of a minimum weight perfect matching in $G$. This question is easy to answer in RNC with inverse-polynomial probability of error using the algorithm Note that the RNC algorithm of [MVV87] also finds a minimum weight perfect matching with high probability; however, unlike the weight, the latter is not guaranteed to be the same with any sizable probability. of [MVV87]. Therefore, using this RNC algorithm in place of the oracle, we get an RNC matching algorithm with the property that in a run, all queries to the decision problem will be answered correctly with overwhelming probability. Whenever the latter happens, the algorithm outputs the same (unique) perfect matching. Hence this is a pseudo-deterministic RNC matching algorithm.

All known efficient matching algorithms for general graphs follow one of two approaches: given by [Edm65] and [Lov79]. Our oracle-based algorithm follows a new approach and uses many of ideas discovered in the last five years. The contributions of various authors is given in detail in Section 2; here we mention two main ingredients. Our algorithm uses the overall structure, as well as an NC algorithm for finding a balanced viable set (see Section 2.3), from the recent NC algorithm of [AV20] for finding a perfect matching in planar graphs. (Since oracle ${\mathcal{O}}$ can be implemented in NC for planar graphs, our current paper yields a simpler NC algorithm for finding a perfect matching in planar graphs.) The second key ingredient is an NC algorithm for finding a maximal laminar family of tight odd sets in a given face of the perfect matching polytope. This follows from the works of [CGS12] and [San18].

${\mathcal{O}}$ will represent the oracle that answers, in one step, the decision question: Given a graph $G$ with small weights and a number $W$, is there a perfect matching of weight at most $W$ in $G$?

There is an NC algorithm for finding a MWPM in general graphs with small weights, provided the algorithm is given access to oracle ${\mathcal{O}}$ for the decision problem. The latter is: Given a graph $G$ with small weights and a target weight $W$, is there a perfect matching of weight at most $W$ in $G$?

There is an NC algorithm for finding a maximum matching in general graphs, provided the algorithm is given access to oracle ${\mathcal{O}}$.

There is a pseudo-deterministic RNC algorithm for finding a minimum weight perfect matching in general graphs with small weights.

We further show that our algorithm only need to call the decision oracle for minors of the input graph.

Let ${\mathcal{F}}$ be a minor-closed family of graphs. If there is an NC algorithm for deciding whether a perfect matching of weight at most $W$ exists in graphs from ${\mathcal{F}}$, weighted with polynomially small weights, then there is also an NC algorithm for finding a MWPM in such graphs.

The recent surge in activity on this problem was initiated by the elegant work of [FGT16] giving a quasi-NC algorithm for perfect matching in bipartite graphs. The essential idea underlying their algorithm is to give a partial derandomization of the Isolation Lemma. In the process, they introduced some powerful ideas which were crucially used in later works and are detailed in Section 2. This was followed by the quasi-NC algorithm of [ST17] for non-bipartite graphs. This work clarified the basic difficulty encountered in such graphs and ways of dealing with them; see Section 2 for details.

The very first result on obtaining parallel matching algorithms was that the decision problem, of determining if a graph has a perfect matching, can be solved in RNC. This is a folklore result – it follows in a straightforward manner from Lovasz’s [Lov79] matching algorithm and Csanky’s result [Csa76] that the determinant of a matrix can be computed in NC.

The first RNC algorithm for the search problem, of actually finding a perfect matching, was obtained by [KUW86]. This was followed by a simpler and more versatile algorithm due to [MVV87]; besides perfect matching, it also yielded RNC algorithms for the problem of exact matching (see Section 8) and for finding a MWPM in a graph with small weights. The latter fact is crucially used for obtaining pseudo-deterministic RNC algorithms for bipartite graphs [GG15] and general graphs (current paper). The “philosophy” behind [MVV87] will be useful for dealing with a difficulty that arises in the design of the current algorithm as well, so it is recalled below Under the NC model, any one processor does not even have enough time to read the entire input, and hence can perform only local computations. On the other hand, a perfect matching is a global object, unlike say, a maximal independent set. Further difficulties arise from the fact that the number of perfect matchings in a graph can vary widely, all the way from one to exponentially many (assuming it has at least one). If there were a unique perfect matching in the graph, the algorithm’s task would become a lot simpler. [MVV87] achieve uniqueness via their probabilistic fact, the Isolating Lemma: under an assignment of randomly chosen small weights to the edges it claims that the MWPM will be unique with high probability..

The matching problem occupies an especially distinguished position in the theory of algorithms: Some of the most central notions and powerful tools within this theory were discovered in the context of an algorithmic study of this problem, including the notion of polynomial time solvability [Edm65], the counting class #P [Val79] and a polynomial time equivalence between random generation and approximate counting for self-reducible problems [JVV86], which lies at the core of the Markov chain Monte Carlo method. The perspective of parallel algorithms has also led to such a gain, namely the Isolation Lemma [MVV87], which has found several applications in complexity theory and algorithms; see the Wikipedia page [Wik]. Due to the fundamental insights gained from an algorithmic study of matching, and the possibility of additional insights, the problem of obtaining an NC algorithm for it has remained a premier open question ever since the 1980s.

The first substantial progress on this question was made for the case of planar bipartite graphs by [MN89] via a flow-based approach, followed by [MV00] using the fact that there is an NC algorithm for counting perfect matchings in planar graphs. The long-standing problem of extending this result to non-bipartite planar graphs was resolved by [AV20]. Subsequently, [San18] also got the same result using different ideas. [AV20] also extended their algorithm to constant genus graphs. Subsequently, [EV19] gave an NC algorithm for perfect matching in one-crossing-minor-free graphs, which include $K_{5}$-free graphs and $K_{3,3}$-free graphs; the resolution of the latter class settles an open problem asked in [Vaz89].

The notion of a pseudo-deterministic algorithm with polynomial expected running time was given by [GG11] and was applied to several number theoretic and cryptographic problems. The notion of pseudo-deterministic RNC algorithms was defined by [GG15].

Recently, algorithms were also obtained for the generalization of bipartite matching to the linear matroid intersection problem by [GT17], and to a further generalization of finding a vertex of a polytope with faces given by totally unimodular constraints, by [GTV17].

2 What is the “right” decision problem?

Consider the following two decision problems for perfect matching:

Given a graph $G$ with small weights and a target $W$, is there a perfect matching of weight at most $W$ in $G$?

Clearly, the second can be reduced to the first and is therefore “easier”. This leads to a legitimate question: why not attempt to reduce, in NC, the search problem to the second decision problem? Our experience suggests that the first problem is much more basic for the setting at hand. We next provide evidence to this effect.

Seeking a MWPM in a graph with small weights was the central problem in the work of [MVV87]. The Isolating Lemma helped find small weights under which there was a unique MWPM. The second half of [MVV87] gave an NC algorithm for finding this (unique) perfect matching, using the Tutte matrix of the graph and matrix inversion; the latter is known to be in NC [Csa76]. Ever since then, perhaps the most used avenue for obtaining an NC matching algorithm was to derandomize the Isolating Lemma. This would deterministically yield small weights under which there is a unique MWPM, and it could be found using the second half of [MVV87].

The question of MWPM in a graph with small weights plays a central role in NC-type approaches to all non-bipartite, and even some bipartite, perfect matching algorithms: partial derandomization leading to quasi-NC algorithms [FGT16, ST17], resolution of the open problem of non-bipartite planar graphs [AV20, San18], and quasi-deterministic RNC algorithms for bipartite [GG15] and general graphs (current paper).

In mathematics, sometimes solving a more general problem turns out to be easier than solving the special case, if the former has a better “behavior”. Our belief is that this is the case here. The main avenue studied for solving the second decision problem was by derandomizing polynomial identity testing [??]. However, more than three decades of work on the latter has yielded no substantial results. We believe it is time to wholeheartedly attack the first decision problem. Going forward, that is the main message of our paper.

3 Bipartite vs non-bipartite matching: An intriguing phenomenon

Decades of algorithmic work on the matching problem, from numerous perspectives, exhibits the following intriguing phenomenon: The bipartite case gets solved first. Then, using much more elaborate machinery, involving structural facts and algorithmic insights, the general graph case follows, yielding the exact same result! This phenomenon is made all the more fascinating by the fact that the “elaborate machinery” consists not of one fact but numerous different structural properties and mathematical facts which happen to be just right for the problem at hand! We give a number of examples below.

The duality between maximum matching and minimum vertex cover for bipartite graphs extends to general graphs via the notion of an odd set cover, see [LP09]. The formulation of the perfect matching polytope for bipartite graphs extends by introducing constraints corresponding to odd sets [Edm65]. Polynomial time algorithms for maximum matching and maximum weight matching in bipartite graphs generalize via the notion of blossoms [LP09]. The most efficient known algorithm for maximum matching in bipartite graphs [HK73, Kar73] obtained via an alternating breadth first search, extends via a much more elaborate algorithm with the same running time using the graph search procedure of double depth first search [MV80] and blossoms defined from the perspective of minimum length alternating paths [Vaz94]. The RNC matching algorithms [KUW86, MVV87] use Tutte’s theorem to extend to general graphs. The randomized matching algorithm of [RV89] uses Tutte’s theorem and a theorem of Frobenius about ranks of sub-matrices of skew-symmetric matrices.

More recent work exhibits this phenomenon as well. The quasi-NC algorithm of [FGT16] for bipartite graphs extends by handling tight odd cuts appropriately [ST17]. The NC algorithm of [MV00] for planar bipartite graphs was extended to non-bipartite graphs via Edmonds’ formulation of the perfect matching polytope [Edm65], an NC algorithm for max-flow in planar graphs [Joh87], and a result of [PR82] proving that the Gomory-Hu tree of a graph must contain a tight odd cut, and an elaborate NC algorithm for uncrossing tight odd cuts [AV20]. In the same vein, the current paper is extending the pseudo-deterministic RNC bipartite algorithm of [GG15] by giving a way of dealing with tight odd cuts in Edmonds’ formulation of the perfect matching polytope [Edm65] and using an NC procedure for finding a maximal laminar family of tight odd cuts [CGS12, San18].

Overview and Technical Ideas

Most of this paper will concentrate on the problem of finding a perfect matching in a general graph in NC, given oracle ${\mathcal{O}}$. In Section 6.1 we will extend our ideas to finding a MWPM for small weights; an algorithm for finding a maximum matching in a general graph in NC will easily follow. In this section, we will also give a number of key definitions which will be used throughout the paper.

For ease of comprehension, we will first give an outline of a proof of Theorem 2 for the case of bipartite graphs. Such a proof can be gleaned from the paper of [GG15]; however, to the best of our knowledge, this important fact was not derived so far. Below, we build on the quasi-NC algorithm of [FGT16] to obtain a somewhat simpler proof of this result.

The algorithm of [FGT16] first finds a point in the interior of the perfect matching polytope and then iteratively moves to lower dimensional faces of this polytope, terminating when a vertex of the polytope is reached; this will be a perfect matching.

In a general graph $G=(V,E)$ with edge weight function $w$, an edge $e$ is called an allowed edge if it participates in MWPM. Let $E[w]$ denote the set of all allowed edges. Edges in the complement of this set will be called disallowed edges.

Assume $w$ are small weights and let ${\operatorname{PM}}[w]$ denote the face of the polytope containing all fractional and integral MWPMs w.r.t. $w$. Since we are in the bipartite case, ${\operatorname{PM}}[w]$ has a simple description: It is defined by the set of disallowed edges, since they are set to zero, or equivalently its complement, i.e., the set of allowed edges, $E[w]$. The description of the algorithm given above can be refined to: Iteratively modify the weight vector $w$ so that the dimension of face ${\operatorname{PM}}[w]$ keeps dropping, and equivalently $E[w]$ keeps getting sparser, until $E[w]$ is a perfect matching.

As argued earlier, using oracle ${\mathcal{O}}$, we can find the weight of a MWPM in $G$. Further, it is easy to see that for a given edge $e$, we can determine in NC if $e$ participates in a MWPM, i.e., if $e\in E[w]$. Repeating for all edges in parallel, we get the following easy fact for general graphs as well:

Given a graph $G=(V,E)$ and small weights $w$, and given oracle ${\mathcal{O}}$, we can compute $E[w]$ in NC.

The following is a fundamental notion in all recent NC-type matching algorithms:

([DKR10]) Given a general graph $G$ with edge-weights $w$ and an even cycle $C$ in it, number the edges of $C$ consecutively, starting from an arbitrary edge. Then the circulation of cycle $C$ is the absolute value of the difference of the sum of weights of odd-numbered and even-numbered edges and is denoted by $\operatorname{circ}_{w}(C)$.

It is easy to prove that if the MWPM in $G$ is not unique, then any cycle in the symmetric difference of two such matchings must have zero circulation. It follows that if we find a weight vector $w$ such that each cycle in $G$ has nonzero circulation, then the MWPM must be unique and can be found in NC. The next fact shows how to achieve this one cycle at a time.

([FGT16]) In a bipartite graph, let cycle $C\subseteq E[w]$ have $\operatorname{circ}_{w}(C)=0$. Let $G$ denote the graph on edge set $E[w]$. Assign small weights $w^{\prime}$ to edges $E[w]$ so that $\operatorname{circ}_{w}^{\prime}(C)>0$. Then $C$ will not be present in $E[w^{\prime}]$, i.e., at least one of its edges will be dropped in going from $E[w]$ to $E[w^{\prime}]$. We will say that $C$ got destroyed.

Hence, if we find a weight vector that destroys all cycles of $G$, we would be done. However, $G$ may have exponentially many cycles, so this is non-trivial. One of the key ideas of [FGT16] is a systematic way of destroying cycles: They iteratively destroy cycles of length $4,8,16,\dots,n$; clearly, the number of iterations needed is $O(\log n)$. In the first round, $G$ has at most $O(n^{4})$ cycles of length 4. [FGT16] show that if all cycles of length at most $2^{i}$ have already been destroyed, then there are at most $O(n^{4})$ cycles of length at most $2^{i+1}$ left. Hence, in each iteration only $O(n^{4})$ cycles need to be destroyed.

Suppose the current iteration starts with small weights $w$ under which all cycles of length at most $2^{i}$ have already been destroyed. In this iteration, the algorithm finds a weight vector $w^{\prime}$ for the edges in $E[w]$ under which all cycles of length at most $2^{i+1}$ are destroyed. The following fact will play a central role in the current paper as well:

([FGT16]) In order to destroy any set of $s$ cycles, it suffices to try certain well-chosen $O(n^{2}s)$ integral weight vectors each of which uses numbers that are $O(n^{2}s)$; one of these vectors is sure to work.

Since in the current iteration $s=O(n^{4})$, at most $O(n^{6})$ weight vectors suffice. The algorithm for choosing a weight vector that works is as follows. In parallel, for each of the $O(n^{6})$ weight vectors, $y$, compute $E[y]$ and find the girth of the resulting graph; this can easily be done in NC. Pick the lexicographically first weight vector, say $w^{\prime}$, such that $E[w^{\prime}]$ has girth $>2^{i+1}$. Clearly, $w^{\prime}$ destroys all cycles of length at most $2^{i+1}$.

2 Extension to general graphs

In a wide range of computational models, matching algorithms for general graphs are far harder than for bipartite graphs, mainly because they need to handle odd cycles in special ways. The set of constraints capturing the perfect matching polytope is also more complex: it includes exponentially many odd set constraints. An odd set $S\subset V$ which satisfies this constraint with equality is called a tight odd set. The description of face ${\operatorname{PM}}[w]$ is also much more involved: in addition to edges $E[w]$, we need a maximal laminar family of tight odd sets, say ${\mathcal{L}}$; see Section 3.2.

Analogous to 9, which yielded the “engine” for the bipartite case, there is an “engine” underlying our algorithm as well – it iteratively reduces the size of the graph. This engine can be thought of as composed of three components which draw on different domains to establish structural facts and algorithms.

2.1 Component based on the structure of the perfect matching polytope

We first note that 9 does not hold in general graphs: a non-bipartite graph may have an even cycle $C\subseteq E[w]$ with $\operatorname{circ}_{w}(C)>0$. The reason is the presence of a tight odd set. As a result, 9 needs to be enhanced to the fact stated below. We will say that a cycle $C$ crosses a tight odd set $S$ if $C$ has vertices in $S$ as well as in $(V-S)$. Similarly, edge $e$ crosses $S$ if one of its endpoints is in $S$ and the other is in $V-S$.

([ST17]) In a general graph $G$, suppose even cycle $C\subseteq E[w]$ has $\operatorname{circ}_{w}(C)>0$. Then, there must be a tight odd set $S$ such that $C$ crosses $S$.

This is illustrated in Fig. 2. In this graph, the three edges in $\delta(S)$ have weight 1 and the rest have weight 0. Observe that each edge participates in a MWPM and hence $E[w]$ consists of all edges. The cycle consisting of the four orange edges, say $C$, has positive circulation even though it is contained in $E[w]$. Cycle $C$ crosses tight odd set $S$.

Assume that even cycle $C$ crosses tight odd set $S$. Number the edges of $C$ starting from an arbitrary edge. Let $n_{o}$ and $n_{e}$ denote the number of odd-numbered and even-numbered edges, respectively, that cross $S$. Then the mismatch of C and S, denoted $\operatorname{mismatch}(C,S)$, is $\operatorname{}\mathopen{}\lvert n_{o}-n_{e}\mathclose{}\rvert$.

Note that in Fig. 2, $\operatorname{mismatch}(C,S)=2$. Observe that if the MWPM is not unique and $C$ is a cycle in the symmetric difference of two such perfect matchings then the following must hold:

If $C$ crosses a tight odd set $S$, then $\operatorname{mismatch}(C,S)=0$; the reason is that each perfect matching crosses each tight set exactly once.

(Lemma 27) Consider a general graph $G$ with weights $w$ and even cycle $C\subseteq E[w]$ with $\operatorname{circ}_{w}(C)>0$. Let $S$ be a tight odd set such that $C$ crosses $S$. Then $\operatorname{mismatch}(C,S)>0$ and at least one edge of $C$ has both its endpoints in $S$.

Our strategy for dealing with cycle $C$ having $\operatorname{circ}_{w}(C)>0$ is to shrink the tight odd set $S$ it crosses; this is illustrated in Fig. 2. By 13, this will shrink at least one edge of $C$, hence resulting in a smaller graph. Our overall strategy is as follow: Suppose w.r.t. weight vector $w$, $\operatorname{circ}_{w}(C)=0$. Let $w^{\prime}$ be a weight vector such that $\operatorname{circ}_{w^{\prime}}(C)>0$. If so, [ST17] show that either $C$ must lose an edge in going from $E[w]$ to $E[w^{\prime}]$ or a new odd set $S$ goes tight w.r.t. $w^{\prime}$ such that $C$ crosses $S$. In the latter case, we shrink $S$. In either case we will obtain a smaller graph and in both cases we will say that $C$ is destroyed.

2.2 Component based on graph-theoretic facts

As stated in the Introduction, the overall structure of our algorithm is similar to that of [AV20]. Both algorithms require in each iteration a large enough number of edge-disjoint even cycles whose destruction will result in the removal of a corresponding number of edges. However, in both cases, the graph may have not such cycles. The recourse is to resort to even walks.

([ST17]) We call an ordered list of an even number of edges $C=(e_{1},\ldots,e_{2k})$, not necessarily distinct, that start and end at the same vertex, an even walk if this list traverses either a simple even cycle or two odd cycles with a path joining them; in the latter case, the cycles are traversed once each and the path twice, once in each direction.

The list $C$ of edges of an even walk contains each edge either once or twice, and if it contains an edge $e$ twice, then both copies will have the same parity. The notions of circulation and mismatch can be extended to even walks in a natural way by taking into consideration multiplicity of edges. Thus if $e$ occurs twice in walk $C$, is odd-numbered and crosses tight odd set $S$, then it contributes 2 to $n_{o}$ in the computation of $\operatorname{mismatch}(C,S)$ (see Definition 12) and it contributes $2w_{e}$ to the sum of odd-numbered edges in the computation of $\operatorname{circ}_{w}(C)$ (see Definition 8). As shown in [ST17], all statements made above about destroying even cycles carry over to even walks as well.

[AV20] critically used Euler’s formula and the planar dual of $G$ for first finding a large number of edge-disjoint cycles in NC. If more than half were even, they sufficed. Otherwise, they paired up odd cycles and found paths connecting each pair to obtain even walks. This was done in a such a manner that the resulting even walks were edge-disjoint.

Finding edge-disjoint cycles in a general graph in NC appears to be quite difficult. Instead, we take a cue from the bipartite case, which finessed the issue of finding edge-disjoint cycles by using 9. As a result, showing the existence of cycles sufficed! However, there is a subtle difference: in the bipartite case, we needed to upper bound the number of cycles that needed to be destroyed in each iteration, whereas here we need to lower bound them; the latter is the case in [AV20] as well.

Using ideas from [CPR03] we show that if the graph $G=(V,E)$ is not very sparse (see Definition 33), then it contains $\Omega\operatorname{}\mathopen{}\left\lparen\frac{\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert}{\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert}\mathclose{}\right\rparen$ edge-disjoint even cycles. Then, using ideas from [AV20], we show how to pair up odd cycles to form walks. Unlike [AV20], the walks don’t need to be found explicitly – establishing existence suffices.

If in an iteration the graph is very sparse, it will not have the required number of edge-disjoint cycles. For this case, we define the notion of a triad in Definition 23; this is a tight odd set consisting of three vertices. We show that the graph has sufficiently many disjoint triads, and a maximal independent set algorithm can find a large enough subset of these in NC. These can be shrunk simultaneously.

2.3 Component based on facts from matching theory

Suppose that in a certain iteration our algorithm is trying weight function $w$, as per 9. We will need to find in NC a description of face ${\operatorname{PM}}[w]$, which involves, in addition to edges $E[w]$, a maximal laminar family of tight odd sets, say ${\mathcal{L}}$. As stated in Fact 7, computing $E[w]$ using oracle ${\mathcal{O}}$ is straightforward. However, finding family ${\mathcal{L}}$ in NC is a difficult question. The difficulty is similar to that of finding a perfect matching in a graph, i.e., the presence of a plethora of solutions. Recall the “philosophy” of [MVV87] given in Section 1.1, for dealing with this issue for perfect matching, namely attempt to narrow down the choices to one. Clearly unlike [MVV87], randomization is not a resource we can use for this purpose. The solution involves imposing more and more restrictions on the family of tight odd sets until it becomes unique! These restrictions arise from deep structural facts from matching theory. Additional facts lead to an NC algorithm for computing ${\mathcal{L}}$ with the help of ${\mathcal{O}}$. These ideas are from [CGS12] and [San18] and are given in Section 3.2.

For the “correct” weight function, say $w$, among the set of even walks being handled in this iteration, some will be destroyed by losing an edge and some by crossing a tight odd set. By updating the edge set to $E[w]$, we can accrue the advantage from the first set of walks. For obtaining advantage from the second set of walks, for each such walk, say $C$, we need to shrink a tight odd set, say $S$, that it crosses. A major obstacle is that our algorithm does not “know” any of the walks! The way we finesse this difficulty is to shrink all outermost sets of ${\mathcal{L}}$, which are clearly disjoint, in the graph on edge set $E[w]$.

Finally, among all weight functions, we will pick the one, say $w$, that yields a graph with the smallest number of edges. There is no guarantee that $w$ would have destroyed all $s$ walks which we had established the existence of up-front. However, at least one of the weight functions must have done so and therefore led to a decrease of at least $s$ edges. Hence, $w$ must also decrease at least $s$ edges, and that suffices for making progress. As shown in Lemma 44, the number of non-isolated edges gets reduced by a factor of $1-\Omega(1/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ in each iteration.

3 The final idea: balanced viable set

Our current strategy is to iteratively reduce the number of edges until a perfect matching remains. After picking its edges, we need to recursively find a perfect matching in each of the shrunk sets (after removing its matched vertex). The resulting algorithm would have polylogarithmic depth; however, it does not run in polylogarithmic time because of the following inherent sequentiality: Perfect matchings in shrunk sets can be found only after finding a perfect matching in the shrunk graph, because the algorithm needs to know the vertex in $S$ that is matched outside $S$. Moreover, perfect matchings in the shrunk graph and the shrunk sets need to be found via a recursive application of the full algorithm described so far.

The exact same issue arose in [AV20] as well. The solution proposed there was meant for general graphs and hence it works here as well. The solution is quite elaborate and hence is not repeated here; instead, we direct the reader to Section 4.2 in [AV20]. We note that the task is somewhat easier here because we have recourse to oracle ${\mathcal{O}}$; [AV20] had to resort to computing Pfaffians orientations, etc. We give a short, high-level summary below.

An odd set $S$ is viable if there is at least one perfect matching in $G$ which picks exactly one edge from $\delta(S)$. A set $S$ is balanced if both $S$ and its complement contain a constant fraction of the vertices. [AV20] show how to find in NC a balanced viable odd set. Let $S$ be such a set. Clearly, using oracle ${\mathcal{O}}$, we can find an edge $e\in\delta(S)$ which is the unique edge in a perfect matching from this cut. Now we are done by a simple divide-and-conquer strategy: match $e$, remove its end-points and find perfect matchings in the two sides of the cut recursively, in parallel. Observe that even though perfect matchings in the two sides can be found only after finding the matched edge $e$, the latter can be done without any recursive calls, hence, leading to a polylogarithmic running time.

Preliminaries

We represent undirected graphs by $G=(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges. Unless otherwise specified, we only work with graphs that have no loops, i.e., an edge from a vertex to itself. An edge between vertices $u$ and $v$ is represented as $\operatorname{}\mathopen{}\{u,v\mathclose{}\}$. For a set $S\subseteq V$, we use $\delta(S)$ to denote the cut between $S$ and its complement, i.e., $\delta(S)=\operatorname{}\mathopen{}\{\operatorname{}\mathopen{}\{u,v\mathclose{}\}\in E\mathrel{}\mathclose{}|\mathopen{}\mathrel{}u\in S,v\notin S\mathclose{}\}$. When $S$ is a singleton, i.e., $\operatorname{}\mathopen{}\{v\mathclose{}\}$ for some $v\in V$, we use the shorthand $\delta(v)=\delta(\operatorname{}\mathopen{}\{v\mathclose{}\})$. A perfect matching is a subset of edges $M\subseteq E$ such that for all $v\in V$ we have $\operatorname{}\mathopen{}\lvert M\cap\delta(v)\mathclose{}\rvert=1$.

We call an edge $e=\operatorname{}\mathopen{}\{u,v\mathclose{}\}$ isolated if $\deg(u)=\deg(v)=1$.

By this definition a graph is a perfect matching if it has no isolated vertices and all of its edges are isolated.

Note that $P[w]$ is a face of $P$; all faces of $P$ can be obtained as $P[w]$ for appropriately chosen $w$.

Given a graph $G=(V,E)$, we call a subset of edges $M\subseteq E$ a perfect matching if it contains exactly one edge in every degree cut, i.e., $\operatorname{}\mathopen{}\lvert M\cap\delta(v)\mathclose{}\rvert=1$ for all $v$. We call a graph matching-covered if any of its edges can be extended to a perfect matching.

A graph $G=(V,E)$ is matching-covered if for every edge $e\in E$, there exists a perfect matching $M$ such that $e\in M$.

Clearly the perfect matchings of $G$ are in one-to-one correspondence with the vertices of this polytope.

When $G$ is clear from context, we simply use ${\operatorname{PM}}$ to refer to this polytope. ${\operatorname{PM}}$ is alternatively described by the following set of linear equalities and inequalities [Edm65]:

Any face $F$ of ${\operatorname{PM}}$ can be either described by a weight vector $w$, i.e., $F={\operatorname{PM}}[w]$, or it can be alternatively described by the set of inequalities turned into equalities in Eq. 1. These correspond to odd sets $S$ and edges $e$. When face $F$ is clear from context, we call odd sets whose inequalities have been turned into equalities, tight odd sets. We call an edge $e$ allowed if $x_{e}>0$ for some $x\in F$, i.e., if the inequality corresponding to $e$ in Eq. 1 has not been turned into equality. We use $E[w]$ or $E[F]$ to denote the set of allowed edges in the face $F={\operatorname{PM}}[w]$. Putting it all together, to describe a face $F$ it is enough to describe the set of allowed edges as well as tight odd sets.

2 Finding a description of a face

A key step in our oracle-based algorithm is: given small weights $w$, compute a description of the face $F={\operatorname{PM}}[w]$. As stated before, using oracle ${\mathcal{O}}$, $E[w]$ can be computed in NC. However, as far as tight odd sets go, there are typically exponentially many choices of a family of such sets that suffice. At this point, it will be useful to recall the “philosophy” of [MVV87] given in Section 1.1, namely when designing an NC algorithm, faced with a plethora of solutions, one should attempt to narrow down the choices to one. Clearly unlike [MVV87], randomization is not a resource we can use for this purpose. The solution to this puzzle is indeed one of the keys that enables our result and is described below. It involves imposing more and more structure on the family of tight odd sets we seek until it becomes unique! It turns out that the latter can be computed in NC with the help of ${\mathcal{O}}$.

Two tight odd sets $S_{1},S_{2}\subseteq V$ are said to cross if they are not disjoint and neither is a subset of the other. A family of these sets ${\mathcal{L}}\subseteq 2^{V}$ is said to be laminar if no pair of sets in it cross. It is well-known that each face $F$ of the perfect matching polytope can be described by the set of allowed edges and a laminar family of tight odd sets ${\mathcal{L}}$:

This definition gives dual solutions for the linear program $\min\operatorname{}\mathopen{}\{\operatorname{}\mathopen{}\langle w,x\mathclose{}\rangle\mathrel{}\mathclose{}|\mathopen{}\mathrel{}x\in{\operatorname{PM}}\mathclose{}\}$ that satisfy complimentary slackness and are in laminar form. By complimentary slackness, for any such solution, $\sum_{S\in{\mathcal{L}}}\pi(S)$ is equal to the weight of a MWPM. Laminar optimal dual solutions exist but are still not unique.

[CGS12] showed that extra conditions can be imposed on laminar optimal dual solution to make it unique. They studied the notion of balanaced critical dual solutions and they showed how this unique ${\mathcal{L}}$ can be found by computing primal solutions to the MWPM problem. [San18] used this procedure to design an alternative NC algorithm for planar graph perfect matching. We describe this procedure below. For more details see the work of [CGS12]. Note that we will not use these rather complex and elaborate extra conditions in any other context, so we will not state them explicitly.

If $E[w]$ is connected, then a balanced critical dual is unique and Algorithm 1 finds its support, the laminar family ${\mathcal{L}}$.

It was observed by [San18] that all steps of Algorithm 1 can be performed in NC except for finding allowed edges $E[w]$ and the computation of $\mu(v)$’s. We note that using oracle ${\mathcal{O}}$, both these steps can be also be performed in NC.

When $E[w]$ is not connected, Algorithm 1 still works but should be run in parallel for each connected component of $E[w]$.

3 Contraction of tight odd sets, matching minors, and triads

[Edm65] observed that if a collection of tight odd sets are disjoint, one can shrink each one to a single node and obtain a smaller graph whose perfect matchings can be extended to perfect matchings in the original graph. For the sake of completeness we state and prove this fact here.

Suppose that $F={\operatorname{PM}}[w]$ is a face of the matching polytope for $G=(V,E)$ and $S_{1},\dots,S_{k}$ are tight odd sets w.r.t. $F$. Let $H$ be obtained from $G$ by removing disallowed edges and contracting each $S_{i}$ to a single node. Then any perfect matching in $H$ can be extended to a perfect matching in $G$.

Note that the graph $H$ obtained above is a minor of the graph $G$. But it is not an arbitrary minor. It has the additional property that every perfect matching of it can be extended back to a perfect matching of the original graph. For convenience we name these minors, matching minors.

A matching minor $H$ of a graph $G$, is a graph that can be obtained by a sequence of the following operations: Pick a face of the matching polytope and a collection of disjoint tight odd sets. Remove disallowed edges, and contract each tight odd set into a single node.

The following statement follows directly from 20.

If $H$ is a matching minor of the graph $G$, then every perfect matching in $H$ can be extended to a perfect matching in $G$.

In our algorithms, we use the simple observation that a path of length $2$ on vertices of degree $2$ yields a tight odd set for the entire matching polytope. We call these paths triads.

A triad in graph $G=(V,E)$ is a set of three vertices $\operatorname{}\mathopen{}\{a,b,c\mathclose{}\}$ such that $\deg(a)=\deg(b)=\deg(c)=2$, and $\operatorname{}\mathopen{}\{a,b\mathclose{}\},\operatorname{}\mathopen{}\{b,c\mathclose{}\}\in E$.

A triad $\operatorname{}\mathopen{}\{a,b,c\mathclose{}\}$ is a tight odd set for the matching polytope and all of its faces.

The only two neighbors of $b$ are $a,c$. So in every perfect matching, $b$ must be matched to one of them. The other vertex must have an edge to an outside vertex, and in fact that is the only possible edge in $\delta(\operatorname{}\mathopen{}\{a,b,c\mathclose{}\})$. ∎

Note that the proof of Lemma 24 does not use the assumptions $\deg(a)=\deg(c)=2$ and only uses $\deg(b)=2$. We will use these extra assumptions elsewhere, to prove that in certain situations, we can find many triads in our graph.

4 Even walks and weight vectors

Even walks were defined in Definition 14. For an even walk $C$, define the signature of $C$ to be the vector:

The notions of circulation and mismatch can be stated in terms of signature:

Now, there cannot be two distinct points $x,y\in{\operatorname{PM}}[w]$ whose difference $x-y$ is a multiple of ${\operatorname{sign}}(C)$, since otherwise we would have $\operatorname{}\mathopen{}\langle w,x\mathclose{}\rangle\neq\operatorname{}\mathopen{}\langle w,y\mathclose{}\rangle$. Another way of stating this is that if $x\in{\operatorname{PM}}[w]$, then $x+\epsilon{\operatorname{sign}}(C)\notin{\operatorname{PM}}[w]$ for any $\epsilon\neq 0$. So, some inequality or equality describing ${\operatorname{PM}}[w]$ must be violated for this point. If we pick $x$ to be in the relative interior of the face ${\operatorname{PM}}[w]$ we will have some slack for non-tight inequalities describing ${\operatorname{PM}}[w]$. So the violated constraint for $x+\epsilon{\operatorname{sign}}(C)$ must be a constraint that is tight for the entire face ${\operatorname{PM}}[w]$. This implies that:

Let $C$ be an even walk with $\operatorname{circ}_{w}(C)>0$. Then either there is an edge $e\in C$ that is disallowed, i.e., $e\notin E[w]$, or for any laminar dual $({\mathcal{L}},\pi)$ describing ${\operatorname{PM}}[w]$, there is some set $S$ such that $\operatorname{mismatch}(C,S)>0$.

For a more detailed proof of this, see [AV20]. Note that if $\operatorname{mismatch}(C,S)>0$, then $C$ must have an edge with both endpoints inside $S$.

Suppose that $C$ is an even walk and $S$ is a tight odd set such that $\operatorname{mismatch}(C,S)>0$. Then there is an edge $e=\operatorname{}\mathopen{}\{u,v\mathclose{}\}\in C$ such that $u,v\in S$.

If this is not true, then every time $C$ enters $S$ it must immediately exit. So if we compute $\operatorname{mismatch}(C,S)$ by looking at edges that cross $S$, we always get a $+1$ followed by a $-1$, and a $-1$ followed by a $+1$. So the entire sum would be $0$ which is a contradiction. ∎

We also borrow from [FGT16] the following important result, which is also stated in [ST17] and as 9 in this paper.

There is a polynomial sized family of polynomially bounded weight vectors ${\mathcal{W}}$, such that for any set of edge disjoint even walks $C_{1},\dots,C_{k}$, there is some $w\in{\mathcal{W}}$ which ensures

This lemma is actually proved in [FGT16, ST17] for any collection of nonzero vectors, not just ${\operatorname{sign}}(C_{i})$’s, as long as there is both a polynomial bound on the number of vectors and the absolute value of their coordinates. Edge-disjointness of even walks automatically puts a bound of $\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$ on their number, and the coordinates of our even walks are always bounded in absolute value by $2$. ∎

5 Maximal independent sets

Given a graph $G=(V,E)$, we call a subset $S\subseteq V$ independent if no edge $e\in E$ has both endpoints in $S$. We call an independent set maximal if no strict superset $T\supsetneq S$ is independent. We will crucially use the fact that maximal independent sets can be found in NC.

There is a deterministic NC algorithm that on input graph $G=(V,E)$ returns a maximal independent set $S\subseteq V$.

We usually want a large, rather than a maximal, independent set. We will use the fact that in bounded degree graphs, any maximal independent set is automatically large.

If $G=(V,E)$ is a graph with $\deg(v)\leq\Delta$ for all $v\in V$, then any maximal independent set $S\subseteq V$ satisfies

The Decision Oracle

We now list several deterministic NC primitives based on ${\mathcal{O}}$. Versions of these two lemmas appear implicitly, stated for planar graphs, in [San18], but we prove them for the sake of completeness.

An edge $e=\operatorname{}\mathopen{}\{u,v\mathclose{}\}$ can be in a MWPM if and only if ${\mathcal{O}}(G,w)=w_{e}+{\mathcal{O}}(G-\operatorname{}\mathopen{}\{u\mathclose{}\}-\operatorname{}\mathopen{}\{v\mathclose{}\},w)$, where $G-\operatorname{}\mathopen{}\{u\mathclose{}\}-\operatorname{}\mathopen{}\{v\mathclose{}\}$ is obtained from $G$ by removing vertices $u,v$. This can be checked in parallel for all edges $e$. ∎

As was observed by [San18], all steps of Algorithm 1 can be run in NC except for finding $E[w]$ and computing $\mu(v)$. Given access to ${\mathcal{O}}$, we can find $E[w]$ in NC by Lemma 31. Furthermore observe that for any $v\in V$

which can be computed by making all queries ${\mathcal{O}}(G-\operatorname{}\mathopen{}\{u\mathclose{}\}-\operatorname{}\mathopen{}\{v\mathclose{}\},w)$ in parallel and then taking the minimum. ∎

An implementation for the oracle, in RNC with arbitrarily small inverse polynomial probability of error for general graphs, follows from [MVV87], since they give an RNC algorithm for finding a MWPM for small weights. Since ${\mathcal{O}}$ is promised to be called at most polynomially many times, the probability of error over the entire run of the algorithm can be made inverse polynomially small.

Structural Facts

Our algorithm requires two structural facts, one for the case that the graph $G$ is very sparse and the other for the complementary case. They are encapsulated in Lemmas 34 and 36.

A connected graph $G=(V,E)$ is said to be very sparse if $\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert<\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert/(1-\epsilon)$, for some constant $\epsilon<1/9$.

If $G=(V,E)$ is a matching-covered, very sparse graph, then the number of triads in any maximal set of node-disjoint triads in $G$ is at least $c_{1}\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$, for some constant $c_{1}(\epsilon)>0$.

The proof of this lemma involves two steps: first, we prove that the total number of triads is large and second, that a maximal node-disjoint set of triads must also be large. The first step is accomplished in the following lemma.

Suppose that $G=(V,E)$ is a graph with no vertices of degree $0$ or $1$. Then the number of triads in $G$ is at least $9\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert-8\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$.

Consider a charging scheme, where we allocate a budget of $1$ to each edge, and the edge distributes its budget between its two endpoints. We then sum up the charge on all vertices and use the fact that this sum is exactly $\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$.

Let $e=\operatorname{}\mathopen{}\{u,v\mathclose{}\}$ be an edge. If neither $u$ nor $v$ is of degree $2$, let the edge give $1/2$ to $u$, and $1/2$ to $v$. If both $u$ and $v$ are of degree $2$, we allocate the budget the same way by splitting it equally between $u$ and $v$. The only remaining case is when one of $u$ and $v$ has degree $2$ and the other has degree at least $3$; by symmetry let us assume that $\deg(u)=2$ and $\deg(v)\geq 3$. Then we allocate $5/8$ to $u$ and $3/8$ to $v$.

Now let us lower bound the charge that each vertex $v$ receives. Note that the minimum amount $v$ receives from any of its adjacent edges is $3/8$, so an obvious lower bound is $3\deg(v)/8$. If $\deg(v)\geq 3$, this is at least $9/8$. Now consider the case when $\deg(v)=2$. Then $v$ receives at least $1/2$ from each of its adjacent edges. If one of the neighbors of $v$ is not of degree $2$, then the charge that $v$ receives will be at least $1/2+5/8=9/8$. The only possible case where $v$ does not receive at least $9/8$ is when it is of degree $2$, and both of its neighbors are also of degree $2$ (the center of a triad), in which case it receives $1$.

Now let $k$ be the number of triads. Then, by the above argument the total charge on all the vertices is at least

Rearranging yields $k\geq 9\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert-8\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$. ∎

We know that the number of triads is at least $9\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert-8\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert=(1-9\epsilon)\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$. Now consider the conflict graph of triads, where nodes represent triads, and edges represent having an intersection. It is easy to see that any triad can only intersect at most $4$ other triads. So the degrees in this conflict graph are bounded by $4$. By 30, any maximal node-disjoint set of triads will contain at least $(1-9\epsilon)\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert/5$ many triads. So we can take $c_{1}(\epsilon)=(1-9\epsilon)/5$ which is positive for $\epsilon<1/9$. ∎

If $G=(V,E)$ is a matching-covered graph on $\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert>2$ vertices that is not very sparse, then there exist $c_{2}\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$ edge-disjoint even walks in $G$, for some constant $c_{2}(\epsilon)>0$.

We first show that there are many edge-disjoint cycles in a non-sparse graph. If at least half of them are even, we are done. Otherwise, we show how to pair up odd cycles and connect them via suitable paths to get sufficiently many edge-disjoint even walks. A proof of the next lemma can be found in [CPR03]; however, for the sake of completeness we provide it here.

In a graph $G=(V,E)$ there exists a collection of edge-disjoint cycles with at least the following number of cycles:

We prove this by induction on $\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert+\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$. We have several cases:

If there are any loops in the graph, we extract that as one of our cycles, and remove the edge from the graph. The promised quantity goes down by $1/(2\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ which is $\leq 1/2$. So from now on we assume that $G$ has no loops.

If there are any two parallel edges $e,e^{\prime}$, we extract those as a cycle of length $2$, and remove both from the graph. The promised number of edge-disjoint cycles goes down by $2/(2\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)\leq 1$. So adding the cycle we extracted fulfills the promise. From now on we assume that $G$ is simple.

If $G$ has any vertices of degree $0$: We can simply remove it and the promised quantity grows.

If $G$ has a vertex of degree $1$: We can also remove this vertex. This operation does not change the numerator but shrinks the denominator, which results in a larger promised quantity.

If $G$ has a vertex $v$ of degree $2$: Let $e,e^{\prime}$ be the two adjacent edges to $v$. Remove $v,e,e^{\prime}$ from the graph, and place a new edge $e^{\prime\prime}$ between the two former neighbors of $v$. By doing this, both $\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$ and $\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$ go down by $1$. So now the promised number of edge-disjoint cycles becomes larger. By induction we find them, and now we replace the edge $e^{\prime\prime}$ if it is used at all in a cycle, by the path of length two consisting of $e,e^{\prime}$. Since $e^{\prime\prime}$ appears in at most one cycle, this operation preserves edge-disjointness.

Finally if $G$ is a simple graph with no vertices of degree $\leq 2$, it must have a cycle of length at most $2\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$. If we prove this, we are done by induction, because we can remove the edges of this cycle and the promised quantity goes down by at most $1$. Now to prove the existence of this cycle, assume the contrary, that the length of the minimum cycle of the graph is at least $2\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert+1$. Pick a vertex $v$ and look at all simple paths of length at most $\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$ going out of $v$. The number of paths of length $i$ is at least twice the number of paths of length $i-1$. This is because every path of length $i-1$ ending at a vertex $u$ can be extended in at least $\deg(u)-1\geq 2$ ways, and none of these extensions will intersect themselves, otherwise we would get a cycle of length $\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert+1$. So in the end, the total number of such paths will be $>2^{\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert}=\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$, which means that two of the paths must share an endpoint. But now from the union of these two paths, we can extract a cycle of length at most $\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert+\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert=2\log_{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$.

If at least half of the cycles guaranteed by Lemma 37 are odd, we need to pair them up and connect them with paths. We use a spanning tree to do this.

Consider a tree $T$ with an even number of tokens placed on its vertices, with possibly multiple tokens on each vertex. There is a pairing, i.e., a partitioning of tokens into partitions of size two, such that the unique tree paths connecting each pair are all edge-disjoint.

Now for each pair of odd cycles $C_{1},C_{2}$ whose tokens got paired up, we create an even walk. Let $P$ be the tree path connecting tokens from $C_{1}$ and $C_{2}$. If $P$ has no common edges with $C_{1},C_{2}$ we can simply create our even walk, but this is not guaranteed to happen. So instead, traverse $P$ from $C_{1}$’s token to $C_{2}$’s token and look at the last exit from $C_{1}$; afterwards look for the first time any vertex of $C_{2}$ is visited. This portion of $P$ is a subpath connecting $C_{1}$ and $C_{2}$ having no common edged with either. We use $C_{1},C_{2}$ and this subpath of $P$ to create our even walk.

First note that if our graph is not an isolated edge and is matching-covered it must contain at least one even cycle. This is so because there must be at least two perfect matchings in the graph, and in their symmetric difference, we can find one such cycle.

Because we are guaranteed to have at least $1$ cycle, we can simply show that asymptotically we can extract $\Omega(\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ edge-disjoint even walks. Then the asymptotic statement translates to the more concrete bound of $c_{2}\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$.

If $(1-\epsilon)\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert\geq\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$, by Lemma 37, we have

cycles. If at least half of them are of even length, we are done. Otherwise we get $\Omega(\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert/\log\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ odd cycles. Perhaps by throwing away one of them, we can assume the number of odd cycles we have is even. Then we can apply Lemma 39 to obtain $\Omega(\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ edge-disjoint walks. This completes the proof. ∎

The Oracle-Based Algorithm

In this section we describe our oracle-based algorithm for finding a perfect matching. In Section 6.1, we will extend this to finding a minimum weight perfect matching for small weights.

On input $G=(V,E)$, our algorithm proceeds by finding smaller and smaller matching minors $H$ of $G$, until $H$ has a unique perfect matching, or in other words is a perfect matching. Then we pick the edges in $H$ as a partial matching in $G$ and extend this partial matching to a perfect matching independently and in parallel for the preimage of each node in $H$. That is for each node $s$ in $H$, we take the set $S\subseteq V$ that got shrunk to $s$, remove the single endpoint of the partial matching from $S$, and recursively find a perfect matching in $S$. In the end we return the results of all these recursive calls along with the edges of $H$ as the final answer.

We crucially make sure that the pre-image of nodes in $H$ never contain more than a constant fraction of $V$. This makes sure that our recursive calls end in $O(\log\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ steps.

In all of our algorithms, when we construct matching minors, we implicitly maintain the mapping from the resulting edges to the original edges, and the mapping from original vertices to the minor’s vertices. These are trivial to maintain in NC, but for clarity we avoid explicitly mentioning them. We also keep node weights for matching minors, where the weight of a node is simply the number of original vertices that got shrunk to it.

The pseudocode for the main algorithm PerfectMatching can be seen in Algorithm 2. On input $G$, the algorithm calls PartialMatching to find a matching minor $H$ of $G$ which itself is a perfect matching. Then the edges of $H$, which form a partial matching in $G$, are extended to a perfect matching independently and in parallel in the preimage of each node from $H$. Since $H$ is a matching minor, this extension can always be performed by Lemma 22.

The pseudocode for PartialMatching can be seen in Algorithm 3. This algorithm keeps a node-weighted matching minor of the input graph $G$. It tries several ways of obtaining a smaller matching minor, where size of a matching minor is measured in terms of the number of non-isolated edges, see Definition 15. One way of obtaining a smaller matching minor is by picking a maximal node-disjoint set of triads and shrinking them simultaneously. By Lemma 24, this produces a matching minor. Also note that the maximal set of node-disjoint triads can be found in NC by enumerating all triads and using Theorem 29.

Another way of obtaining smaller matching minors is by trying weights from the set of weight vectors ${\mathcal{W}}$ and calling Reduce to remove disallowed edges $e\notin E[w]$ and shrinking top-level sets of a laminar family of tight odd sets w.r.t. $w$.

Finally. the pseudocode for Reduce can be seen in Algorithm 4. This algorithm is simply fed a graph $G=(V,E)$ and a weight vector $w$. It removes disallowed edges $e\notin E[w]$ and shrinks the maximal sets of a laminar family of tight odd set. The laminar family is found using Algorithm 1, but is modified to make sure that no shrunk set becomes too large; to be more precise no shrunk vertex in the end will have node weight more than half of the total node weight.

We extend our algorithm so it returns not just any perfect matching, but rather a minimum weight perfect matching, for small weights.

Given an input graph $G=(V,E)$ and a weight vector $w$, we can remove disallowed edges $e\notin E[w]$, and find a laminar family of tight odd sets ${\mathcal{L}}$ w.r.t. $w$, by calling Algorithm 1 on each connected component of $G$. By complementary slackness, any perfect matching that has only one edge in $\delta(S)$ for each $S\in{\mathcal{L}}$ will automatically be of minimum weight, see Definition 17. We can simply contract the top level sets in ${\mathcal{L}}$, use Algorithm 2 to find a perfect matching in the shrunk graph, and recursively extend this to a minimum weight perfect matching in each shrunk piece. Following an almost identical argument as in the proof of 20, the perfect matching in the shrunk graph can be extended to a minimum weight perfect matching.

The only problem with this method is that the recursion depth is not guaranteed to be polylogarithmic. However we can fix that by making sure that tight odd sets $S\in{\mathcal{L}}$ do not have more than half of the vertices in the graph; if they do, we replace them by their complements and we will see in Lemma 42 why this operation preserves laminarity.

2 Minor-closed families of graphs

Throughout our algorithm we only call the decision oracle on graphs obtained from the original through a sequence of edge and vertex removals and contractions. In this section we will prove that the decision oracle is only called on minors of the original graph, that is those graphs obtained by vertex and edge removals and contractions of connected subgraphs.

Algorithms 4, 3 and 2 call the decision oracle on minors of their input graph only.

This lemma is all we need to prove Theorem 5. Note that there are several minor-closed families of graphs where the decision problem can be solved in NC by using a counting oracle. In particular we can count perfect matchings in graphs embedded on surfaces of genus at most $O(\log n)$, and therefore solve the decision problem, all in NC. This improves upon the genus bound of $O(\sqrt{\log n})$ given by [AV20].

For graphs embedded on a surface of genus at most $O(\log n)$ and weighted with polynomially bounded edge weights, there is an NC algorithm to find a minimum weight perfect matching.

Another consequence of Theorem 5 is an alternative algorithm for $K_{3,3}$-free graphs, which was resolved earlier by [EV19].

First we prove this for Algorithm 4. In this algorithm, we only remove edges from the input graph, and shrink tight odd sets in connected components. We just have to show that what we shrink is already connected. Consider a tight odd set $S$ in a connected component $C$. If it is not internally connected, then one of its internal connected components must have odd size; let that be $S^{\prime}$. Since $S\subseteq C$ and $C$ is a connected component, there is an edge $e\in\delta(S-S^{\prime})$. Since $S^{\prime}$ is not internally connected to $S-S^{\prime}$, it must be that $e\in\delta(S)$ too. Now since the graph is matching-covered with minimum weight perfect matchings, there must be some minimum weight perfect matching $M\ni e$. But because $S^{\prime}$ is odd, there must also be an edge $f\in M\cap\delta(S^{\prime})$. But note that $e\neq f$, and both $e,f\in\delta(S)$. This is a contradiction, since $S$ cannot have more than one edge in a perfect matching. This shows that $S$ must be connected and Algorithm 4 only produces minors of its input graph.

Next we prove the statement for Algorithm 3. This algorithm either calls Algorithm 4, or finds triads and contracts them. The former produces minors of the input graph, and the latter also produces minors of the input graph since triads are connected.

Note that the graph returned by Algorithm 3 may not be a proper minor of the input graph; that could happen if the node weight of some $v$ goes above $1/6$ the total node weight. In this scenario, the complement of $v$ might not be connected and yet we contract it. However the algorithm immediately returns and the decision oracle is not called on this returned graph. So this does not contradict the statement of the lemma.

Finally we prove the statement for Algorithm 2. The only graphs produced and passed onto Algorithm 3 are obtained from the input graph by vertex removals and edge removals. So they are all minors of the input graph. The output of Algorithm 3 might not be a proper minor, but this output is only used to decide which edges and vertices to remove from the original graph to get to induced graphs on $S-\operatorname{}\mathopen{}\{v\mathclose{}\}$. ∎

Analysis of the algorithm

First we will prove that our oracle-based algorithm returns a correct answer. Next, we will bound the running time and prove that our algorithm runs in NC, modulo the calls to ${\mathcal{O}}$; this constitutes the most challenging part of the analysis.

Suppose that ${\mathcal{L}}$ is a laminar family of sets in a node-weighted graph $G=(V,E)$, and we replace every $S\in{\mathcal{L}}$ whose node weight is larger than half of the total node weight by the complement, i.e., $V-S$. Then the resulting family of sets ${\mathcal{L}}^{\prime}$ is also laminar.

Let $S,S^{\prime}$ be two sets in ${\mathcal{L}}$. They are either disjoint or one is contained in the other.

If $S\cap S^{\prime}=\emptyset$: They cannot both have node weight more than $1/2$. So at most one of them gets replaced by its complement. Then it is easy to see that the resulting sets do not cross.

If $S\subseteq S^{\prime}$: There are three possibilities. If none of them gets replaced by their complements, or both of them get replaced by their complements, they remain nested and therefore do not cross. If one of them gets replaced by its complement, it has to be the larger set $S^{\prime}$. In that case the resulting sets become disjoint, and still do not cross. ∎

Using Lemma 42 and Lemma 22, we deduce that Reduce always returns a matching minor of its input graph. By definition, PartialMatching also returns a matching minor of its graph when it finishes (for the analysis of running time see Section 7.2).

This proves the correctness of the algorithm, since we always find a matching minor that has a unique perfect matching (itself), and by Lemma 22, we can extend it to a perfect matching, independently in the preimage of each node.

2 Running time

First we analyze PerfectMatching (Algorithm 2) assuming the calls to PartialMatching (Algorithm 3) are in NC.

Assuming the calls to PartialMatching are in NC, then the procedure PerfectMatching is in NC.

We simply need to bound the number of levels in the recursion. To do so, we will prove that when PartialMatching returns a matching minor $H$, the node weight of every node is at most $5/6$ the total node weight. This proves that in each recursive call to PerfectMatching, the number of vertices gets reduced by a factor of $5/6$.

Note that the first time in Algorithm 3 that a node’s weight goes above $1/6$ the total weight, the algorithm stops and returns a two-node minor. So we just need to prove that the weight of the node that just went above $1/6$ is not more than $5/6$. The current minor was obtained from the previous minor by either Reduce, or by shrinking triads. But Reduce never creates nodes with weight more than half the total weight. The weight of each node in a triad is also at most $1/6$ the total weight, so after shrinking the triad, the new weight can be at most $1/6+1/6+1/6=1/2$ the total weight. This finishes the proof. ∎

Finally, we need to prove that PartialMatching finishes in a polylogarithmic number of steps. Using the structural facts, Lemma 44 and Lemmas 34 and 36, we establish the following lemma.

In each iteration of Algorithm 3, the number of non-isolated edges gets reduced by a factor of $1-\Omega(1/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$.

First assume $G$ is a connected graph. Then we can directly apply Lemmas 34 and 36 for some fixed $\epsilon<1/9$ to show that we either find $c_{1}\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert$ triads or there exist $c_{2}\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$ edge-disjoint even walks. In the former case, after contracting the triads, the number of edges gets reduced by a factor of $1-c_{1}$. In the latter case, let $C_{1},C_{2},\dots,C_{k}$ be the edge-disjoint even walks, and let $w\in{\mathcal{W}}$ be the weight vector such that $\operatorname{}\mathopen{}\langle w,{\operatorname{sign}}(C_{i})\mathclose{}\rangle\neq 0$. Note that $w$ is guaranteed to exist by Lemma 28. In the call to $\textnormal{{{Reduce}}}(G,w)$, every $C_{i}$ loses at least edge by Lemmas 26 and 27, either because one of its edges becomes disallowed or it gets shrunk as a result of shrinking top-level tight odd sets. Therefore, one of the candidate graphs in $U$ in Algorithm 3 will have a factor of $1-c_{3}/\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$ fewer edges, for some constant $c_{3}>0$.

Next assume $G$ is not connected. If so, we apply the above-stated argument to each connected component that is not an isolated edge. We can further assume the same weight vector $w$ works for all connected components. Now if $H_{1}$ is the graph obtained from shrinking triads, and $H_{2}$ is the result of $\textnormal{{{Reduce}}}(G,w)$, then we know that the average number of edges in $H_{1}$ and $H_{2}$ for each connected component is at most $1-c_{3}/2\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert$ times the number of edges in the connected component. So one of $H_{1},H_{2}$ must have at most $(1-c_{3}/2\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ times as many non-isolated edges as $G$. ∎

Note that Lemma 44 gives a polylogarithmic upper bound on the number of iterations in Algorithm 3, since if we track the number of non-isolated edges, after every $\Theta(\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ steps we get a constant factor reduction, and therefore it takes at most $O(\log\operatorname{}\mathopen{}\lvert E\mathclose{}\rvert\cdot\log^{2}\operatorname{}\mathopen{}\lvert V\mathclose{}\rvert)$ iterations for it to reach $0$.

Discussion

This paper has identified what appears to be the “core” of the difficult open problem of obtaining an NC matching algorithm, namely the decision problem. We must immediately mention that both decision problems stated in Section 1.2 have been the subject of numerous attacks over the past decades and hence resolution is not likely to be an easy matter. At the same time, we hope that since the “target” has been more precisely identified, the resolution of the open problem will gain added impetus.

An obvious open question is to build on the quasi-NC algorithms of [GT17, GTV17] to obtain the appropriate oracle-based NC algorithms and pseudo-deterministic RNC algorithms for linear matroid intersection and for finding a vertex of a polytope with faces given by totally unimodular constraints. An interesting problem defined by Papadimitriou and Yannakakis [PY82] , called Exact Matching, is the following: Given a graph $G$ with a subset of the edges marked red and an integer $k$, find a perfect matching with exactly $k$ red edges. This problem is known to be in RNC [MVV87], even though it is not yet known to be in ¶. Is there a pseudo-deterministic RNC algorithm for it?

The phenomenon identified in Section 1.3 clearly deserves to be studied in depth. To the best of our knowledge, there are only two algorithmic results for bipartite matching that have not been extended to general graphs. The first is obtaining a fully polynomial randomized approximation scheme for counting the number of perfect matchings [JSV04]; this is also among the outstanding open problems of theoretical computer science today. The second is obtaining an $O(m^{11/8})$ algorithm for maximum matching [LS20], which beats the earlier algorithms for sparse graphs.

References