Planar Graph Perfect Matching is in NC

Introduction

Is perfect matching in $\mathsf{NC}$? That is, is there a deterministic parallel algorithm that computes a perfect matching in a graph in polylogarithmic time using polynomially many processors? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of $\mathsf{RNC}$ matching algorithms [KUW86, MVV87]. Within this question, the case of planar graphs had remained an enigma: For general graphs, counting the number of perfect matchings is far harder than finding one: the former is #$\mathsf{P}$-complete [Val79] and the latter is in $\mathsf{P}$ [Edm65a]. However, for planar graphs, a polynomial time algorithm for counting perfect matchings was found by Kasteleyn, a physicist, in 1967 [Kas67], and an $\mathsf{NC}$ algorithm follows easily For a formal proof, in a slightly more general context, see [Vaz89]., given an $\mathsf{NC}$ algorithm for computing the determinant of a matrix, which was obtained by Csanky [Csa76] in 1976. On the other hand, an $\mathsf{NC}$ algorithm for finding a perfect matching in a planar graph has resisted a solution. In this paper, we provide such an algorithm.

An $\mathsf{RNC}$ algorithm for the decision problem, of determining if a graph has a perfect matching, was obtained by Lovász [Lov79], using the Tutte matrix of the graph. The first $\mathsf{RNC}$ algorithm for the search problem, of actually finding a perfect matching, was obtained by Karp, Upfal, and Wigderson [KUW86]. This was followed by a somewhat simpler algorithm due to Mulmuley, Vazirani, and Vazirani [MVV87].

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 [Edm65a] and the counting class #$\mathsf{P}$ [Val79]. The parallel perspective has also led to such gains: The first $\mathsf{RNC}$ matching algorithm led to a fundamental understanding of the computational relationship between search and decision problems [KUW85] and the second algorithm yielded the Isolation Lemma [MVV87], which has found several applications in complexity theory and algorithms. Considering the fundamental insights gained by an algorithmic study of matching, the problem of obtaining an $\mathsf{NC}$ algorithm for it has remained a premier open question ever since the 1980s.

The first substantial progress on this question was made by Miller and Naor in 1989 [MN89]. They gave an $\mathsf{NC}$ algorithm for finding a perfect matching in bipartite planar graphs using a flow-based approach. In 2000, Mahajan and Varadarajan gave an elegant way of using the $\mathsf{NC}$ algorithm for counting perfect matchings to finding one, hence giving a different $\mathsf{NC}$ algorithm for bipartite planar graphs [MV00]. Our algorithm is inspired by their approach.

In the last few years, several researchers have obtained $\mathsf{quasi\text{-}NC}$ algorithms for matching and its generalizations; such algorithms run in polylogarithmic time though they require $O(n^{\log^{O(1)}n})$ processors. These algorithms achieve a partial derandomization of the Isolation Lemma for the specific problem addressed. Several nice algorithmic ideas have been discovered in these works and our algorithm has benefited from some of these; in turn, it will not be surprising if some of our ideas turn out to be useful in the resolution of the main open problem. First, Fenner, Gurjar, and Thierauf gave a $\mathsf{quasi\text{-}NC}$ algorithm for perfect matching in bipartite graphs [FGT16], followed by the algorithm of Svensson and Tarnawski for general graphs [ST17]. Algorithms were also found for the generalization of bipartite matching to the linear matroid intersection problem by Gurjar and Thierauf [GT16], and to a further generalization of finding a vertex of a polytope with faces given by totally unimodular constraints, by Gurjar, Thierauf, and Vishnoi [GTV17].

There is an $\mathsf{NC}$ algorithm which given a planar graph, returns a perfect matching in it, if it has one.

In section 7 we generalize theorem 1 to finding a minimum weight perfect matching if the edge weights are polynomially bounded and to finding a perfect matching in graphs of bounded genus; their common generalization easily follows.

Overview and Technical Ideas

We first give the idea behind the $\mathsf{NC}$ algorithm of Mahajan and Varadarajan for bipartite planar graphs. W.l.o.g. assume that the graph is matching covered, i.e., each edge is in a perfect matching. Using an oracle for counting the number of perfect matchings, they find a point $x$ in the interior of the perfect matching polytope and they show how to move this point to lower dimensional faces of the polytope until a vertex is reached; this will be a perfect matching. In a matching covered bipartite planar graph, every face (in a planar embedding) is the symmetric difference of two perfect matchings and modifying $x$ by increasing and decreasing alternate edges by the same (small) amount $\epsilon$ moves the point inside the polytope; we will call this a rotation of the cycle. Keep increasing $\epsilon$, starting from 0, until some edge $e$ on this cycle attains $x_{e}=0$; in this case, $e$ is dropped. When this happens, $\epsilon$ cannot be increased anymore and we will say that the cycle is blocked. If so, the point $x$ moves to a lower (by at least one) dimension face. To make substantial progress, they observe that for any set of edge-disjoint faces, this process can be executed independently (by different amounts) in parallel on cycles corresponding to each of the faces, thereby reaching a face of the polytope of correspondingly lower dimension. Finally, they show how to find $\Omega(n)$ edge-disjoint faces in $\mathsf{NC}$, thereby terminating in $O(\log n)$ such iterations.

The fundamental difference between the perfect matching polytopes of bipartite and non-bipartite graphs is the additional constraint in the latter saying that each odd subset, $S$, of vertices must have a total of at least one edge in the cut $\delta(S)$ (see LP (1) in section 3.2). This constraint introduces a second way in which a cycle $C$ can be blocked, namely some odd set $S$, whose cut intersects $C$, may go tight (section 5.1) and the $\epsilon$ introduced for this cycle cannot be increased any more (without moving the point outside the polytope and making it infeasible). If so the cycle will not lose an edge. However, notice that since one of the odd set constraints has gone tight, we are already at a face of one lower dimension! In this case, we will say that cycle $C$ is blocked by odd set $S$. For an example, see fig. 1 in which the point inside the polytope is the all $1/3$ vector and highlighted cycle is blocked by odd set $S$. Observe that the rotation chosen on the highlighted cycle leads to infeasibility on cut $S$.

How do we capitalize on this progress though? The obvious idea (which happens to need substantially many additional ideas to get to an $\mathsf{NC}$ algorithm) is to shrink $S$, find a perfect matching in the shrunk graph, expand $S$, remove from it the vertex that is matched to a vertex in $V-S$, and find a perfect matching on the remaining vertices of $S$. For an example of the shrunk graph, see fig. 2. It is easy to see that at least one edge of $C$ must have both endpoints in $S$, and therefore the shrunk graph is smaller than the original graph.

As stated above, a number of new ideas are needed to make this rough outline yield an $\mathsf{NC}$ algorithm. First, a small hurdle: If $G$ is non-bipartite planar, the procedure of Mahajan and Varadrajan will find $\Omega(n)$ edge-disjoint faces; however, not all of these faces may be even. In fact, there are matching covered planar graphs having only one even face. To get around this, we define the notion of an even walk: it consists of two odd faces with a path connecting them; for convenience, we will call an even cycle an even walk as well (section 3.3). We give an $\mathsf{NC}$ algorithm for finding $\Omega(n)$ edge-disjoint even walks in $G$ (section 6.2). Furthermore, it is easy to see that rotating an even walk also moves point $x$ inside the perfect matching polytope (this is done in lemma 9).

2 A key algorithmic issue and its resolution

As in the case of a cycle, a walk is blocked either if it loses an edge or if an odd cut intersecting it goes tight. In either case, the point moves to a face of lower dimension. However, a new algorithmic question arises: In the first case, the amount of rotation required to make the walk lose an edge is easy to compute, similar to the bipartite case. But in the second case, how do we find the smallest rotation so an odd cut intersecting the walk goes just tight? Note that we seek the “smallest” rotation so no odd cut goes under-tight. We will postpone the answer to this question until we address the next hurdle.

Next, we state a big hurdle: As in the bipartite case, to make substantial progress, we need to move the point $x$ to a face of the polytope where each of the $\Omega(n)$ even walks is blocked. Recall that in the bipartite case, we could modify all of the edge-disjoint even cycles independently in parallel and, the resulting point still remains in the matching polytope. However, in the non-bipartite case, executing these moves in parallel may take the point outside the polytope, i.e., it becomes infeasible. These two cases are illustrated in fig. 3 and fig. 4, respectively. The reason for the latter is that whereas rotations on two different walks may be individually feasible, executing them both may make an odd set go under-tight. This is made explicit in fig. 5 in which the two walks can individually be rotated by $\epsilon_{1}$ and $\epsilon_{2}$, respectively, without violating feasibility. However, executing them both simultaneously makes odd set $S$ go under-tight.

The following idea, which can be considered the main new idea in our work, helps us get around this hurdle: It suffices to find a weight function on edges, $w$, so that one of the half-spaces defined by $w$ contains the vector $w$ itself and the other contains, for each of the even walks, the direction of motion resulting from its rotation. Then, the minimizer of $x\mapsto\langle w,x\rangle$ in the polytope will lie in a face at which each of the walks is blocked either because it has lost an edge or it intersects a tight odd cut. Furthermore, the minimizer is still a feasible point, so no odd cut goes under-tight. This idea is illustrated in fig. 6. The two yellow arrows indicate independent moves on two edge-disjoint walks which lead to two different faces of the polytope. Executing them both simultaneously would take the point outside the polytope, as was illustrated in fig. 4. However, the minimizer of $\langle w,x\rangle$ lies on a face of the polytope at which both the walks are blocked.

The weight function $w$ is obtained as follows: The traversal of an even walk gives an ordered list of edges, possibly with repetition, of even length. W.r.t. a weight function $w$, define the circulation of an even walk to be the difference of sum of weights of even and odd numbered edges in the traversal of this walk (section 5.1). We show that any weight function $w$ that makes the circulation of each of the even walks non-zero suffices in the following sense: Given such a function $w$, we can pick a direction of rotation for each of the even walks so that one of the half-spaces defined by $w$ contains the vector $w$ and the other contains the direction of motion of each of the even walks (lemma 10). Moreover, such a function $w$ is easy to construct: in each walk, pick the weight of any one edge to be 1 and the rest 0 (section 4.2).

Next, we need to find the minimizer of $w$ in the polytope. For this, it suffices to construct an $\mathsf{NC}$ oracle for computing $\#G^{e}_{w}$, the number of minimum weight matchings in $G$ containing the edge $e$. This oracle is constructed by finding a Pfaffian orientation (section 3.1) for $G$, appropriately substituting for the variables in the Tutte matrix of $G$ and computing the determinant of the resulting matrix (section 6.1).

Some clarifications are due at this point: First, let us answer the opening question of this section, i.e., how to rotate just one given walk so it gets blocked by one of the two ways? Interestingly enough, at present we know of no simpler method for one walk than for multiple walks (binary search comes to mind but that is not an elegant, analytic solution). Second, in the bipartite case, either one of two measures of progress works when we simultaneously rotate many edge-disjoint cycles: the number of edges removed or the decrease in the dimension of the face we end up on. In the non-bipartite case, if rotating a walk leads to an odd cut going tight, we will shrink the cut, as stated above. As stated above, at least one edge of the walk will be in the odd set and will get shrunk. So, for the case of a single walk, both measures of progress stated above still work. However, when we rotate $k$ edge-disjoint walks, say, and none of these walks loses an edge, then the dimension of the face we end up on may not be smaller by $O(k)$. The reason is that very few, or even one, odd cut may intersect each of the walks. However, each walk will have at least one edge in a tight odd set, and therefore shrinking them will result in $O(k)$ edges being shrunk. Hence, the first measure of progress still works.

3 The rest of the ideas

A number of ideas are still needed to get to an $\mathsf{NC}$ algorithm. First, for each walk that does not lose an edge, we need to find a tight odd cut intersecting it. For this, we use the result of Padberg and Rao [PR82] stating that the Gomory-Hu tree of a graph will contain a minimum weight odd cut. We show how to find a Gomory-Hu tree in a weighted planar graph in $\mathsf{NC}$ (section 6.3), a result of independent interest. Next, consider a walk $W$ which, w.r.t. the current point $x$ in the polytope, is intersecting a tight odd cut. We rotate walk $W$ further slightly so the point $x$ becomes infeasible, i.e., $W$ now crosses an under-tight cut, or perhaps several of them (lemma 10). Observe that rotating a walk leaves each singleton cut tight. Hence, w.r.t. $x$, each minimum weight odd cut must be an under-tight cut that crosses $W$, and the Gomory-Hu tree must contain one of them. Repeating this for all walks in parallel, we obtain a set of tight odd cuts that intersect each of the walks.

However, these odd cuts cannot be shrunk simultaneously because they may be crossing each other. We know there is a laminar family of tight odd cuts, but how do we find it in $\mathsf{NC}$? We next give a divide-and-conquer-based procedure that finds the top level sets of one such laminar family; these top level sets can clearly be shrunk simultaneously (section 5.2). The procedure works as follows: We partition the family of tight odd cuts into two (almost) equal subfamilies, recursively “uncross” each subfamily to obtain its top level sets, and then merge these two into one family of top level sets. Clearly the last step is the crux of the procedure. The key to it lies in observing that two families of top level sets have a simple intersection structure, which can be exploited appropriately.

The proposed algorithm has now evolved to the following: shrink all top level sets and recursively find a perfect matching in the shrunk graph, followed by recursively finding a perfect matching in each of the shrunk sets (after removing its matched vertex). This algorithm has polylog depth; however, it does not run in polylog time because of the following inherent sequentiality: matchings in the shrunk sets have to be found after finding a matching in the shrunk graph. The reason is that a matching in a shrunk set $S$ can be found only after knowing the vertex in $S$ that is matched outside $S$, and this will be known only after finding a matching in the shrunk graph. We next observe that if we could find a balanced tight odd cut, we would be done by a simple divide-and-conquer strategy: match any edge in the cut and find matchings in the two sides of the cut recursively, in parallel. The task of finding a balanced tight odd cut is not straightforward though. It involves iteratively shrinking the top level sets found, finding even walks and moving to the minimum weight face in the shrunk graph, etc. (section 4.2). This is illustrated in fig. 7. We show that $O(\log n)$ such iterations suffice for finding a balanced tight odd cut.

Preliminaries

In this section, we will state several notions and algorithmic primitives we need for our $\mathsf{NC}$ algorithm for finding a perfect matching in a planar graph.

A key fact underlying our algorithm is that computing the number of perfect matchings in a planar graph lies in $\mathsf{NC}$. Let $G=(V,E)$ be an arbitrary graph (not necessarily planar). Let $A$ be the symmetric adjacency matrix of $G$, i.e., corresponding to each edge $(i,j)\in E,\ A(i,j)=A(j,i)=1$, and the entries corresponding to non-edges are zero. Obtain matrix $T$ from $A$ by replacing for each edge $(i,j)\in E$, its two entries by $x_{ij}$ and $-x_{ij}$, so the entries below the diagonal are positive; clearly, $T$ is skew-symmetric. $T$ is called the Tutte matrix for $G$. Its significance lies in that its determinant is non-zero as a polynomial iff $G$ has a perfect matching. However, computing this determinant is not easy: Simply writing it will require exponential space in general.

Next assume that $G$ has a perfect matching. A simple cycle $C$ in $G$ is said to be nice if the removal of its vertices leave a graph having a perfect matching. If so, clearly, $C$ lies in the symmetric difference of two perfect matchings in $G$. Direct the edges of $G$ to obtain $\overrightarrow{G}$. We will say that $\overrightarrow{G}$ is a Pfaffian orientation for $G$ if each nice cycle $C$ has an odd number of edges oriented in each way of traversing $C$. Its significance lies in the following: Let $(i,j)\in E$, with $i<j$. If in the Pfaffian orientation, this edge is directed from $i$ to $j$, then let $x_{ij}=1$, otherwise let $x_{ij}=-1$. Then the determinant of the resulting matrix is the square of the number of perfect matchings in $G$.

Of course, $G$ may not have a Pfaffian orientation. A key fact underlying our algorithm is that every planar graph has a Pfaffian orientation and moreover, such an oriantation can be found in $\mathsf{NC}$ and the determinant can be computed in $\mathsf{NC}$ by Csanky’s algorithm [Csa76]. Hence we can answer the decision question of whether $G$ has a perfect matching in $\mathsf{NC}$.

2 The perfect matching polytope, its faces, and tight odd sets

We use the notation $\mathds{1}_{F}$ to denote the indicator vector of a subset of edges $F\subseteq E$. For a subset of vertices $S$, we let $\delta(S)$ denote the edges that cross $S$, and by a slight abuse of notation we let $\delta(v)=\delta(\{v\})$ denote the set of edges adjacent to vertex $v$.

The perfect matching polytope is the convex hull of indicator vectors of all perfect matchings in $G$ and will be denoted by $\PM(G)$:

One of the key steps needed by our algorithm is finding a point in the relative interior of the face $\PM(G,w)$ in $\mathsf{NC}$. This requires computing a Pfaffian orientation for $G$ and then evaluating the Tutte matrix for appropriate substitutions of the variables. The point we find will be exactly the average of the vertices, i.e., $\mathds{1}_{M}$ for perfect matchings $M$, lying on the face $\PM(G,w)$. We denote this average by $\avg(\PM(G,w))$:

In general, a face of $\PM(G)$ is defined by setting a particular set of inequalities to equalities. Let $\cal S$ be the family of odd sets whose inequalities are set to equality. These will be called tight odd sets. Two such tight odd sets $S_{1},S_{2}\in\cal S$ are said to cross if they are not disjoint and neither is a subset of the other. If so, one can prove that either $S_{1}\cap S_{2}$ and $S_{1}\cup S_{2}$ are also tight odd sets or $S_{1}-S_{2}$ and $S_{2}-S_{1}$ are tight odd sets. In the former case one can remove the equality constraint for $S_{1}$ and replace it by the equality constraints for $S_{1}\cap S_{2}$ and $S_{1}\cup S_{2}$, and the face would not change. In the latter case $S_{1}$ can be replaced by $S_{1}-S_{2}$ and $S_{2}-S_{1}$ and still the face remains invariant. In either case, the new sets do not cross. The family $\cal S$ is said to be laminar if no pair of sets in it cross. Given a family of tight odd sets $\cal S$, one can successively uncross pairs to obtain a family of tight odd sets defining the same face of the polytope. This operation will result in a laminar family. However, for our purposes, we only need to work with the maximal sets in the laminar family. We define a similar notion of uncrossing for such top-level sets and show how they give us the space of equality constraints, by defining things appropriately.

3 Finding maximal independent sets and even walks

One of the ingredients we use in multiple ways to design our algorithm is that a maximal independent set in a graph can be found in $\mathsf{NC}$.

There is an $\mathsf{NC}$ algorithm for finding some maximal independent set in an input graph $G=(V,E)$.

Mahajan and Varadarajan used lemma 2 to find linearly many edge-disjoint cycles in bipartite planar graphs [MV00]. We use a similar step, but instead of cycles we have to work with even walks, i.e., cycles with possibly repeated edges.

For this paper, an even walk is either a simple even length cycle in $G$ or the following structure: Let $C_{1}$ and $C_{2}$ be two odd length edge-disjoint cycles in $G$ and let $P$ be a path, edge-disjoint from $C_{1},C_{2}$, connecting vertex $v_{1}$ of $C_{1}$ to vertex $v_{2}$ of $C_{2}$; if $v_{1}=v_{2}$, $P$ will be the empty path. Starting from $v_{1}$, traverse $C_{1}$, then $P$ from $v_{1}$ to $v_{2}$, then traverse $C_{2}$, followed by $P$ from $v_{2}$ to $v_{1}$. This will be a walk that traverses an even number of edges and will also be called an even walk.

Note that all of our walks start and end at the same location. We use lemma 2 to derive the following. We prove lemma 3 in section 6.2.

Suppose that $G=(V,E)$ is a connected planar graph with no vertices of degree $1$ and at most $\lvert V\rvert/2$ vertices of degree $2$. Then we can find $\Omega(\lvert E\rvert)$ edge-disjoint even walks in $G$ by an $\mathsf{NC}$ algorithm.

Main Algorithm

In this section we will describe the algorithm we use to prove theorem 1. W.l.o.g. assume that the input graph has a perfect matching. We can easily check whether a perfect matching exists first, by counting the number of perfect matchings in $\mathsf{NC}$; see section 3.1.

We use a divide-and-conquer approach. The pseudocode is given in algorithm 1. Given a graph $G=(V,E)$, our algorithm finds an odd set $S\subset V$, selects an edge $e\in\delta(S)$ as the first edge of the perfect matching, and then recursively extends this to a perfect matching in $S$ and $V-S$, without using any other edge of the cut $\delta(S)$.

Note that if $M$ is the output of our algorithm, by definition, $\lvert M\cap\delta(S)\rvert=1$. This prevents us from using an arbitrary odd set $S\subset V$ in the first step and motivates the following definition.

Given a graph $G=(V,E)$, an odd set $S$ is called viable if there exists at least one perfect matching $M\subseteq E$ with $\lvert M\cap\delta(S)\rvert=1$.

In order for a step of the algorithm to make significant progress, i.e., reduce the size of the graph by a constant factor, we also require the viable set to be balanced. That is, we require

for some small constant $c_{1}>0$. Throughout the paper we will assume several constant upper bounds for $c_{1}$. At the end $c_{1}$ can be set to the lowest of these upper bounds.

Assuming that we are able to find a balanced viable set $S$ in $\mathsf{NC}$, we can prove theorem 1.

Since the set $S$ found by algorithm 1 is feasible, there is at least one perfect matching $N$ with $\lvert N\cap\delta(S)\rvert=1$. On the other hand, for the weight vector $w=\mathds{1}_{\delta(S)}$ and any perfect matching $N$, we have $\langle w,\mathds{1}_{N}\rangle=\lvert N\cap\delta(S)\rvert$, which is always at least one. So the minimum weight perfect matchings $N$ are exactly those that have a single edge in the cut $\delta(S)$. The point $x$ is the average of these perfect matchings, so for any edge $e$ with $x_{e}>0$, there is at least one minimum weight perfect matching $N\ni e$. This shows that $\{e\}$ can be extended to a perfect matching without using any other edge of $\delta(S)$ and therefore proves that $G_{1}$ and $G_{2}$ both have a perfect matching, an assumption we need to be able to recursively call the algorithm. This shows the correctness of the algorithm.

We finish the proof by showing that the algorithm is in $\mathsf{NC}$. By lemma 1, we can compute the point $x$ in $\mathsf{NC}$, and we assumed the viable set $S$ was found by an $\mathsf{NC}$ algorithm. So all of the steps of each recursive call can be executed in polylogarithmic time with a polynomially bounded number of processors. Notice that the recursion depth of the algorithm is at most $\log_{1/(1-c_{1})}(\lvert V\rvert)$ which is logarithmic in the input size. This is because the size of the graph gets reduced by a factor of $1-c_{1}$ in each recursive level. Since recursive calls are executed in parallel, this shows that the entire algorithm runs in polylog time. ∎

All that remains is finding a balanced viable set by an $\mathsf{NC}$ algorithm. This is done in section 4.2.

2 Finding a balanced viable set

In this section we describe how to find a balanced viable set $S$ in a graph $G=(V,E)$ by an $\mathsf{NC}$ algorithm. Notice that a single vertex is, by definition, a viable set, but is not balanced unless $\lvert V\rvert\leq\frac{1}{c_{1}}$. So w.l.o.g. we can assume $\lvert V\rvert>\frac{1}{c_{1}}$.

The main idea behind our algorithm is the following: Suppose that we reduce the size of the graph $G$ by either removing edges not participating in perfect matchings from it, or shrinking tight odd sets (both w.r.t. some weight vector $w$). Any vertex in the shrunk graph corresponds to an odd set in the original graph $G$. This odd set is always viable. So if we manage to reduce the size of the shrunk graph enough so that it contains at most $1/c_{1}$ vertices, then the largest of the viable sets we get this way would have size at least $c_{1}\lvert V\rvert$. By being careful when we remove edges or shrink pieces, we can also make sure the size is not larger than $(1-c_{1})\lvert V\rvert$; so the end result is a balanced viable set. See fig. 7 for a depiction.

The pseudocode is given in algorithm 2. Throughout the algorithm we maintain a mapping $f$ from the original vertices to the vertices of the current shrunk graph. We iteratively reduce the size of the graph by removing edges and/or contracting odd sets of vertices until one of the vertices contains a $c_{1}$ fraction of the original vertices. We then return the preimage of this vertex.

The while loop in algorithm 2 finishes as soon as $\lvert V\rvert\leq\frac{1}{c_{1}}$.

So when the number of terms in the sum is below $\frac{1}{c_{1}}$, one of them has to be larger than $c_{1}$. ∎

We further maintain the invariant that our graph $G$ is at all time planar, and has a perfect matching. This invariant is satisfied, because we restrict ourselves to manipulate $G$ in only one of the two following ways:

We either remove an edge $e$ from $G$, where $e$ does not participate in any minimum weight perfect matching for some weight vector $w$.

Or we shrink a set of vertices $S$ that is a tight odd set w.r.t. some point $x$ in the matching polytope.

If a graph $G$ is planar and has a perfect matching, after the removal of an edge or shrinking of a set as described above, it continues to be planar and have a perfect matching.

The lemma is obvious in the case of removing an edge. Planarity is automatically satisfied, and since the edge did not participate in any minimum weight perfect matching, the remaining graph still has a minimum weight perfect matching.

In the case of shrinking a tight odd set, first note that the resulting graph would still have a perfect matching. Indeed, if we look at $x$ after shrinking $S$, it becomes a valid point in the matching polytope of the shrunk graph: The degree constraint of the shrunk vertex is satisfied because the odd set constraint of $S$ was originally tight.

It remains to show why after shrinking $S$, the graph remains planar. If $S$ is internally connected, this follows from the fact that contracting edges preserves planarity. Otherwise, assume that $S=S_{1}\cup S_{2}$ where there are no edges between $S_{1}$ and $S_{2}$. Because $S$ is odd, either $S_{1}$ or $S_{2}$ must be odd, and the other even. W.l.o.g. assume that $S_{1}$ is odd. Note that $\langle\mathds{1}_{\delta(S_{1})},x\rangle\leq\langle\mathds{1}_{\delta(S)},x\rangle$ and equality holds if and only if $S_{2}$ does not have any outgoing edges. But $\langle\mathds{1}_{\delta(S)},x\rangle=1$, and $\langle\mathds{1}_{\delta(S_{1})},x\rangle\geq 1$, so there must be equality.

So when $S$ was not internally connected, we showed that it must be a union of a connected component and a smaller tight odd set. By repeating this argument, we see that $S$ must always be a union of an internally connected odd set and a number of connected components. Now simply note that shrinking an entire connected component with some other vertex preserves planarity. ∎

It is also easy to see that any viable set in the resulting graph is a viable set in the original graph at any point, because any perfect matching in $G$ can be extended to a perfect matching in $G_{0}$. So we can return $f^{-1}(v)$ at any point if it is a balanced set.

The main loop in algorithm 2 has two steps, Preprocess and Reduce. Although not explicitly stated in the pseudocode, at any point in the execution of either step, we can terminate the whole procedure by finding a balanced viable set and directly returning it.

First we preprocess the graph. Below we state the properties we expect to hold after preprocessing. We postpone the description of the procedure Preprocess and the proof of lemma 6 to section 4.3.

The procedure Preprocess either finds a balanced viable set or after it returns the following conditions hold.

No vertex $v\in V$ has degree $1$ and at most half of the vertices have degree $2$.

For all $v\in V$, we have $\lvert f^{-1}(v)\rvert<c_{1}\lvert V_{0}\rvert$.

Now we describe the main step, i.e., Reduce. The pseudocode is given in algorithm 3.

Assuming lemma 6, our goal is to either remove a constant fraction of the edges of $G$ or shrink pieces of $G$ so that a constant fraction of the edges get shrunk. The conditions satisfied after the preprocessing step, lemma 6, ensure that we can apply lemma 3 and find $\Omega(\lvert E\rvert)$ edge-disjoint even walks, as we do in the first step of algorithm 3.

Next, we construct a weight vector which is $0$ everywhere except for the first edge of every even walk, and find a point $x$ in the relative interior of $\PM(G,w)$ by applying lemma 1. By our choice of weight vector, each even walk either loses an edge or gets blocked by a tight odd set as we will prove in section 5. Our last step consists of finding a number of disjoint odd sets $S_{1},\dots,S_{l}$, such that each even walk $W_{i}$, that did not lose an edge, has an edge with both endpoints in one $S_{j}$. We describe the procedure DisjointOddSets and prove these properties in section 5.

After running Reduce we either find a balanced viable set, or $\lvert E\rvert$ gets reduced by a constant factor.

We find $k$ even walks where $k=\Omega(\lvert E\rvert)$. Every walk either loses an edge in the edge removal step, or loses an edge after shrinking $S_{1},\dots,S_{l}$. So the number of edges gets reduced by at least $k$, which is a constant fraction of $\lvert E\rvert$ as long as $\lvert E\rvert$ is large enough (larger than a large enough constant). Note that we never encounter graphs with $\lvert V\rvert<1/c_{1}$ by lemma 4, so by setting $c_{1}$ small enough we can assume that $\lvert E\rvert$ is larger than a desired constant. ∎

By lemma 7, our measure of progress, $\lvert E\rvert$ gets reduced by a constant factor each time until we find a balanced viable set. Therefore the number of times Reduce is called is at most $O(\log(\lvert E_{0}\rvert))$, so as long as DisjointOddSets can be run in $\mathsf{NC}$, the whole algorithm is in $\mathsf{NC}$.

We describe the remaining pieces, Preprocess in section 4.3, and DisjointOddSets in section 5.

3 Preprocessing

Here we describe the procedure Preprocess and prove lemma 6. The pseudocode is given in algorithm 4. Throughout the process, we make sure that $\lvert f^{-1}(v)\rvert<c_{1}\lvert V_{0}\rvert$ for every $v$ or we find a balanced viable set.

In the first step, we remove any edge of $G$ that does not participate in a perfect matching. Next we make the graph connected. We arrive at a connected graph where every edge participates in a perfect matching. This ensures that there are no vertices of degree $1$, unless the entire graph is a single edge; but in that case we return $f^{-1}(v)$ as a balanced viable set for any of the two vertices.

After having a connected graph with no vertices of degree $1$, while half of the vertices have degree $2$, we shrink them into other vertices by finding appropriate tight odd sets. The while loop can be run at most a logarithmic number of times, because each time the number of vertices gets reduced by a factor of $2$.

It remains to describe the procedures MakeConnected and ShrinkDegreeTwos. Both of these procedures work by shrinking tight odd sets w.r.t. $x$. In both, we have to be slightly careful to avoid shrinking a large piece of the original graph causing a violation of the condition $\lvert f^{-1}(v)\rvert<c_{1}\lvert V_{0}\rvert$.

First let us describe MakeConnected. We first find the connected components $C_{1},\dots,C_{k}$ of $G$. We sort them to make sure $\lvert f^{-1}(C_{1})\rvert\leq\dots\leq\lvert f^{-1}(C_{k})\rvert$. Let $v$ be an arbitrary vertex of $C_{k}$. For any $i<k$ the set $S_{i}=\{v\}\cup C_{1}\cup\dots C_{i}$ is a tight odd set, because $\{v\}$ is a tight odd set and adding entire connected components does not change the cut value. If $\lvert f^{-1}(S_{k-1})\rvert<c_{1}\lvert V_{0}\rvert$, then we can simply shrink $S_{k-1}$ into a single vertex and make the graph connected. Otherwise let $j$ be the first index where $\lvert f^{-1}(S_{j})\rvert\geq c_{1}\lvert V_{0}\rvert$. Then $f^{-1}(S_{j})$ is a viable set, because it is a tight odd set. We claim that it is balanced as well; for this we need to show that $\lvert f^{-1}(S_{j})\rvert\leq(1-c_{1})\lvert V_{0}\rvert$. We have

where we used the fact that $C_{j}$ is not the largest component in terms of $f^{-1}(C_{j})$. So as long as $c_{1}+1/2<1-c_{1}$, we are done. This is clearly satisfied for small enough $c_{1}$.

Now let us describe ShrinkDegreeTwos. First we identify all vertices of degree $2$. Some of these vertices might be connected to each other, in which case we get paths formed by these vertices. We can extend these paths, by the doubling trick in polylog time to find maximal paths consisting of degree $2$ vertices. Then, in parallel, for each such maximal path we do the following: Let the vertices of the path be $(v_{1},\dots,v_{k})$. Further, let $v_{0}$ be the vertex we would get if we extended this path from the $v_{1}$ side and $v_{k+1}$ the one we would get from the $v_{k}$ side. Note that $\deg(v_{i})=2$ for $i=1,\dots,k$ but not for $i=0,k+1$.

We claim that for any even $i$, the set $S_{i}=\{v_{0},v_{1},\dots,v_{i}\}$ is a tight odd set. To see this, let $t=x_{(v_{0},v_{1})}$. Then because $v_{1}$ has degree $2$, it must be that $x_{(v_{1},v_{2})}=1-t$. Then, this means that $x_{(v_{2},v_{3})}=t$, and so on. In the end, we get that $x_{(v_{i-1},v_{i})}=1-t$. Now, look at the edges in $\delta(S)$. They are either adjacent to $v_{0}$ or $v_{i}$. Those adjacent to $v_{0}$ have a total $x$ value of $1-t$ and those adjacent to $v_{i}$ have a total $x$ value of $t$. So $\langle\mathds{1}_{\delta(S_{i})},x\rangle=t+(1-t)=1$.

Now let $j$ be the first even index such that $\lvert f^{-1}(S_{j})\rvert\geq c_{1}\lvert V_{0}\rvert$. If no such index exists, we can simply shrink $S_{k}$ or $S_{k+1}$ (depending on the parity of $k$). Else, we claim that $S_{j}$ is a balanced viable set. Viability follows from being a tight odd set. Being balanced follows because

So as long as $3c_{1}\leq(1-c_{1})$, the set $S_{j}$ is balanced and we can simply return it.

Having all of the ingredients, we now finish the proof of lemma 6.

It is easy to see that the point $x\in\PM(G)$ remains a valid point throughout, i.e., it remains in the matching polytope even after shrinking sets. This is because we only shrink tight odd sets w.r.t. $x$. Assume that the algorithm does not find a balanced viable set.

After MakeConnected the graph becomes connected, and from then on it remains connected.

Since $x$ remains a valid point in the matching polytope until the end, every edge at the end participates in a perfect matching. But in a connected graph, this means that there are no vertices of degree $1$.

Finally note that by the stopping condition of the while loop, the algorithm terminates only when at most half of the remaining vertices have degree $2$. ∎

Tight Odd Sets

In this section we describe the main remaining piece of the algorithm, namely the procedure DisjointOddSets. The input to this procedure is a graph $G=(V,E)$ and a map $f:V_{0}\to V$, a number of edge-disjoint even walks $W_{1},\dots,W_{m}$ in $G$, the point $x=\avg(\PM(G,w))$, where $w$ is the weight vector constructed in algorithm 3. Note that $x_{e}>0$ for all $e\in E$, since we removed all edges $e$ with $x_{e}=0$. We will prove the following:

There is an $\mathsf{NC}$ algorithm DisjointOddSets, that either finds a balanced viable set, or finds disjoint tight odd sets $S_{1},\dots,S_{l}$ satisfying the following: In any $W_{i}$ there is an edge $e$ both of whose endpoints belong to some $S_{j}$. Furthermore $\lvert f^{-1}(S_{j})\rvert<c_{1}\lvert V_{0}\rvert$ for all $j$.

At a high level the procedure works as follows:

First, for each even walk $W_{i}$, we find a tight odd set blocking it.

The resulting tight odd sets might cross each other in arbitrary ways. We uncross them to obtain $S_{1},\dots,S_{l}$, being careful not to produce sets with $\lvert f^{-1}(S_{i})\rvert\geq c_{1}\lvert V_{0}\rvert$.

In section 5.1 we describe the procedure for finding a tight odd set blocking an even walk. Then in section 5.2, we describe how to uncross these and produce disjoint odd sets.

In this section we describe how to find a tight odd set blocking a given even walk $W$. At a high level, we first move slightly outside of the polytope by moving along a direction defined by $W$. Then we find one of the violated constraints defining the matching polytope. This must be the tight odd set we were after.

Recall that an even walk is either a simple even length cycle in $G$ or the following structure: Let $C_{1}$ and $C_{2}$ be two odd length edge-disjoint cycles in $G$ and let $P$ be a path connecting vertex $v_{1}$ of $C_{1}$ to vertex $v_{2}$ of $C_{2}$; if $v_{1}=v_{2}$, $P$ will be the empty path. Starting from $v_{1}$, traverse $C_{1}$, then $P$ from $v_{1}$ to $v_{2}$, then traverse $C_{2}$, followed by $P$ from $v_{2}$ to $v_{1}$.

Next we define the alternating vector of an even walk $W$. For this purpose, write $W$ as a list of edges $W=(e_{1},\dots,e_{k})$, where $k$ is even and if the walk contains a path, then the edges of the path will be repeated twice in this list. We define the alternating vector associated to $W$ as the vector $\chi_{W}$ given by

Note that for a weight vector $w$, we have

In particular for the weight vector chosen in algorithm 3, we have $\langle w,\chi_{W}\rangle<0$.

Note that the point $x$ is $\avg(\PM(G,w))$, i.e., we have

where $M_{1},\ldots,M_{m}$ are all the minimum weight perfect matchings in $G$.

We will now see what happens to an $\epsilon$-rotation of this point if $\epsilon$ is small enough.

Let $x=\avg(\PM(G,w))$ for some weight vector $w$. Let $W$ be an even walk whose edges are in the support of $x$, i.e., for every $e\in W$, we have $x_{e}>0$, and let $\langle w,\chi_{W}\rangle<0$. Let $K(n)\leq n^{n}$ denote the number of perfect matchings in the complete graph $K_{n}$, and let $y$ be an $\epsilon$-rotation of $x$ with the walk $W$ for some $\epsilon<1/2nK(n)$. Then, the following hold:

For every vertex $v$, we have $\langle\mathds{1}_{\delta(v)},y\rangle=1$.

For every odd set $S\subset V$, if $\langle\mathds{1}_{\delta(S)},x\rangle>1$, then $\langle\mathds{1}_{\delta(S)},y\rangle\geq 1$.

For every edge $e\in E$, we have $y_{e}\geq 0$.

Condition 1 holds because $\langle\mathds{1}_{\delta(v)},\chi_{W}\rangle=0$. This identity holds, because the walk $W$ enters and exits each vertex $v$ the same number of times, and the entries and exits have alternating signs, cancelling each other.

Condition 2 holds, because when $\langle\mathds{1}_{\delta(S)},x\rangle>1$, then it is larger than $1$ by a margin; choosing $\epsilon$ small enough will not let us erase more than this margin. Formally we have

and note that $\langle\mathds{1}_{\delta(S)},\mathds{1}_{M_{i}}\rangle$ is at least $1$ and must be greater than $1$ for some $i$. For that particular $i$ this value must be at least $2$ (in fact, at least $3$), which gives us

Now, note that $\lVert\chi_{W}\rVert_{1}\leq 2n$ and $\lVert\mathds{1}_{\delta(S)}\rVert_{\infty}\leq 1$ which together imply that

Finally, piecing things together, we have

Condition 3 holds, because again, $x_{e}>0$ implies that $x_{e}$ is positive by a margin. We have

which implies that $y_{e}\geq 1/m-2\epsilon\geq 0$. ∎

Lemma 9 almost ensures that the point $y$ is inside the matching polytope $\PM(G)$ if the starting point $x$ was in $\PM(G)$. The only way that $y$ cannot be in $\PM(G)$ is if there is an odd set $S\subset V$ such that $\langle\mathds{1}_{\delta(S)},x\rangle=1$, i.e., a tight odd set, whose constraint gets violated by $y$. This leads us to the following important lemma, which enables us to extract a tight odd set blocking the rotation of the walk $W$.

Suppose that $w$ is a weight vector, $x=\avg(\PM_{w}(G))$, $W$ is a walk that satisfies the conditions of lemma 9, and furthermore $\langle w,\chi_{W}\rangle<0$. Then there must be an odd set $S\subset V$ such that $\langle\mathds{1}_{\delta(S)},x\rangle=1$ and $\langle\mathds{1}_{\delta(S)},\chi_{W}\rangle\neq 0$. Furthermore such an $S$ can be found by first obtaining $y$ as an $\epsilon$-rotation of $x$ by $W$, for a small but inverse exponentially large $\epsilon$, and then finding a minimum odd cut in $y$:

Since $\langle w,\chi_{W}\rangle<0$ we have $\langle w,y\rangle<\langle w,x\rangle$. We choose the magnitude of $\epsilon$ to be small enough that the conditions of lemma 9 are satisfied. Now, since $x$ was a minimizer of the linear function $x\mapsto\langle w,x\rangle$ over the polytope $\PM(G)$, it must be the case that $y\notin\PM(G)$.

Therefore one of the constraints defining the matching polytope, eq. 1, must not be satisfied for $y$. But lemma 9 ensures that almost all of these constraints are satisfied; the only possible constraint being violated would be an odd set $S$ such that $\langle\mathds{1}_{\delta(S)},x\rangle=1$ and $\langle\mathds{1}_{\delta(S)},y\rangle<1$. Take any such set $S$ where $\langle\mathds{1}_{\delta(S)},x\rangle=1$ and $\langle\mathds{1}_{\delta(S)},y\rangle<1$. We have

which means that $\langle\mathds{1}_{\delta(S)},\chi_{W}\rangle\neq 0$. In other words, $S$ satisfies the statement of the lemma.

It only remains to show that if we take $S$ to be a minimum odd cut in $y$, then $S$ satisfies $\langle\mathds{1}_{\delta(S)},x\rangle=1$ and $\langle\mathds{1}_{\delta(S)},y\rangle<1$. We know that the only possible constraint being violated by $y$ is an odd set constraint, so for the minimum odd cut it must be true that $\langle\mathds{1}_{\delta(S)},y\rangle<1$. On the other hand if $\langle\mathds{1}_{\delta(S)},x\rangle>1$, then we would get a contradiction from condition 2 of lemma 9, because that would imply $\langle\mathds{1}_{\delta(S)},y\rangle\geq 1$. So such a set must satisfy $\langle\mathds{1}_{\delta(S)},x\rangle=1$ and $\langle\mathds{1}_{\delta(S)},y\rangle<1$. ∎

We will say that an odd set $S$ such that $\langle\mathds{1}_{\delta(S)},x\rangle=1$ and $\langle\mathds{1}_{\delta(S)},\chi_{W}\rangle\neq 0$, is a set that blocks the walk $W$. By combining the following lemma with lemma 10, we get that we can find a tight odd set blocking each of our even walks.

There is an $\mathsf{NC}$ algorithm that given a weight planar graph $G$, outputs the minimum odd cut of $G$.

2 Uncrossing tight odd sets

Suppose we are given a list of tight odd sets $S_{1},\dots,S_{m}$ that could cross each other in arbitrary ways.

Note that we can assume from the beginning that for each $i$, $\lvert f^{-1}(S_{i})\rvert\leq\frac{1}{2}\lvert V_{0}\rvert$. If not, we simply replace $S_{i}$ by $V-S_{i}$. We can even further assume that $\lvert f^{-1}(S_{i})\rvert<c_{1}\lvert V_{0}\rvert$; otherwise, we would return $f^{-1}(S_{i})$ as a balanced viable set and end the procedure. Throughout the algorithm we maintain this property.

Our goal is to uncross the sets $S_{1},\dots,S_{m}$, so that we can shrink all of them at the same time. We make progress from shrinking these sets by making sure that each of our even walks has an edge inside at least one of the shrunk sets, so that shrinking reduces the number of edges by at least the number of walks.

Unfortunately, having an edge inside an $S_{i}$ is not a property that is preserved by uncrossing. Instead, we require a stronger property that implies having an edge in one $S_{i}$, and show that this stronger property is preserved by uncrossing. Throughout this section we assume that $x$ is some fixed point in $\PM(G)$ with $x_{e}>0$ for all $e\in E$.

We extend this definition to more than one set $S_{1},\dots,S_{m}$ by letting

Next, we will show that $\chi_{W}$ not being orthogonal to $\Lambda(S_{1},\dots,S_{m})$ implies that $W$ has an edge in one $E(S_{i})$.

Let $W$ be an even walk, and assume that $\chi_{W}\notin\Lambda^{\perp}(S_{1},\dots,S_{m})$. Then there is at least one edge $e\in W$ and at least one $i$ such that $e\in E(S_{i})$.

It is easy to see that $\chi_{W}\notin\Lambda^{\perp}(S_{1},\dots,S_{m})$ implies that there is at least one $i$ such that $\chi_{W}\notin\Lambda^{\perp}(S_{i})$. It follows from definition 3 that there must be some tight odd set $T\subseteq S_{i}$ such that $\langle\mathds{1}_{\delta(T)},\chi_{W}\rangle\neq 0$. We will show that $\langle\mathds{1}_{\delta(T)},\chi_{W}\rangle\neq 0$ implies that there is some $e\in W$ such that $e\in E(T)\subseteq E(S_{i})$.

Suppose the contrary, that no edge $e\in W$ is in $E(T)$. Let $W=(e_{1},\dots,e_{k})$ and note that

Every time that $W$ enters a vertex $v\in T$, it must leave immediately from $T$, or else we would find an edge $e\in E(T)\cap W$. Therefore we can pair up the nonzero $\langle\mathds{1}_{\delta(T)},\mathds{1}_{e_{j}}\rangle$s into consecutive pairs, possibly pairing up the last edge with the first. Since these pairs appear in the sum with alternating signs, they cancel each other, giving us

which is a contradiction. Therefore $W$ must have at least one edge in $E(T)\subseteq E(S_{i})$. ∎

Next we will define our basic uncrossing operations and show that they preserve this nonorthogonality property. Whenever we have two tight odd sets $S_{1}$ and $S_{2}$ we will show that we can uncross them, i.e., replace them by new tight odd sets without shrinking the subspace $\Lambda(S_{1})+\Lambda(S_{2})$. We will use the following uncrossing lemma, which is standard in the literature. We will prove it for the sake of completeness.

If $S_{1}$ and $S_{2}$ are tight odd sets then either $S_{1}\cap S_{2},S_{1}\cup S_{2}$ are tight odd sets and

or $S_{1}-S_{2}$ and $S_{2}-S_{1}$ are tight odd sets and

The following identity holds for any $S_{1}$ and $S_{2}$ and can be easily checked by considering all possible configurations of the endpoints of an arbitrary edge:

We have two cases: Either $\lvert S_{1}\cap S_{2}\rvert$ is odd, or it is even.

Case 1: Assume that $\lvert S_{1}\cap S_{2}\rvert$ is odd. It follows that $\lvert S_{1}\cup S_{2}\rvert$ is also odd. Then by taking the dot product with $x$ we get

where the last inequality follows from the fact that $x\in\PM(G)$ and that $S_{1}\cap S_{2}$ and $S_{1}\cup S_{2}$ are odd sets. Since this inequality is tight it must be the case that $\langle\mathds{1}_{\delta(S_{1}\cap S_{2})},x\rangle=\langle\mathds{1}_{\delta(S_{1}\cup S_{2})},x\rangle=1$, which proves that $S_{1}\cap S_{2}$ and $S_{1}\cup S_{2}$ are tight odd sets. It further follows that

which implies that $\mathds{1}_{\delta(S_{1}-S_{2},S_{2}-S_{1})}=0$, i.e., $\delta(S_{1}-S_{2},S_{2}-S_{1})=0$; this is because $x$ has strictly positive entries. Now we have the desired identity

Case 2: Now assume that $\lvert S_{1}\cap S_{2}\rvert$ is even. We can replace $S_{2}$ by $V-S_{2}$, since $V-S_{2}$ is also a tight odd set. But now $S_{1}\cap(V-S_{2})=S_{1}-S_{2}$ which is an odd set. So it follows from the proof of case 1 that $S_{1}\cap(V-S_{2})$ and $S_{1}\cup(V-S_{2})$ are both tight odd sets and we have

Now observe that $S_{1}\cap(V-S_{2})=S_{1}-S_{2}$ and $S_{1}\cup(V-S_{2})=V-(S_{2}-S_{1})$. Since taking complements does not change either $\delta(\cdot)$ or being a tight odd set, the claim follows. ∎

Now we use lemma 13 to prove the claim that tight odd sets can be uncrossed without shrinking $\Lambda(S_{1})+\Lambda(S_{2})$.

Suppose that $S_{1},S_{2}$ are tight odd sets, i.e., $\lvert S_{1}\rvert,\lvert S_{2}\rvert$ are odd and $\langle\mathds{1}_{\delta(S_{1})},x\rangle=\langle\mathds{1}_{\delta(S_{2})},x\rangle=1$. Then exactly one of the following two conditions holds:

$S_{1}$ and $S_{2}-S_{1}$ are both tight odd sets and

Look at the parity of $\lvert S_{1}\cup S_{2}\rvert$. If $\lvert S_{1}\cup S_{2}\rvert$ is odd, then we claim that case 1 happens. Otherwise, we will show that case 2 happens.

Case 1: $\lvert S_{1}\cup S_{2}\rvert$ is odd. In this case $\lvert S_{1}\cap S_{2}\rvert$ is also odd and it follows by lemma 13 that $S_{1}\cup S_{2}$ is a tight odd set. It is trivial from definition 3 that $\Lambda(S_{1}),\Lambda(S_{2})\subseteq\Lambda(S_{1}\cup S_{2})$ which immediately yields

Case 2: $\lvert S_{1}\cup S_{2}\rvert$ is even. In this case $\lvert S_{1}-S_{2}\rvert$ and $\lvert S_{2}-S_{1}\rvert$ are both odd. Again, from lemma 13 it follows that $S_{2}-S_{1}$ is a tight odd set. It remains to prove that $\Lambda(S_{1})+\Lambda(S_{2})\subseteq\Lambda(S_{1})+\Lambda(S_{2}-S_{1})$. It is enough to prove that $\Lambda(S_{2})\subseteq\Lambda(S_{1})+\Lambda(S_{2}-S_{1})$.

It is enough to show that for any tight odd set $T\subseteq S_{2}$, we have the inclusion $\mathds{1}_{\delta(T)}\in\Lambda(S_{1})+\Lambda(S_{2}-S_{1})$. We again have two cases: Either $\lvert T\cap S_{1}\rvert$ is odd or even.

If $\lvert T\cap S_{1}\rvert$ is even, it follows from lemma 13 that $T-S_{1}$ and $S_{1}-T$ are tight odd sets and

We have $\mathds{1}_{\delta(S_{1}-T)},\mathds{1}_{\delta(S_{1})}\in\Lambda(S_{1})$ and $\mathds{1}_{\delta(T-S_{1})}\in\Lambda(S_{2}-S_{1})$. So $\mathds{1}_{\delta(T)}\in\Lambda(S_{1})+\Lambda(S_{2}-S_{1})$ as desired.

The only case that remains is when $\lvert T\cap S_{1}\rvert$ is odd. In this case we apply lemma 13 to the sets $T$ and $S_{2}-S_{1}$, both of which are tight odd sets. Note that $T\cap(S_{2}-S_{1})=T-S_{1}$ which has even size by assumption. Therefore by lemma 13, $(S_{2}-S_{1})-T$ and $T-(S_{2}-S_{1})=S_{1}\cap T$ are also tight odd sets and

We have $\mathds{1}_{\delta(S_{1}\cap T)}\in\Lambda(S_{1})$ and $\mathds{1}_{\delta(S_{2}-S_{1}-T)},\mathds{1}_{\delta(S_{2}-S_{1})}\in\Lambda(S_{2}-S_{1})$ which proves that $\mathds{1}_{\delta(T)}\in\Lambda(S_{1})+\Lambda(S_{2}-S_{1})$ as desired. ∎

Given tight odd sets $S_{1},\dots,S_{m}$, repeated applications of lemma 14 allow us to uncross them, i.e., replace them by pairwise disjoint tight odd sets $S_{1}^{\prime},\dots,S_{m^{\prime}}^{\prime}$ such that $\Lambda(S_{1},\dots,S_{m})\subseteq\Lambda(S_{1}^{\prime},\dots,S_{m^{\prime}}^{\prime})$. However, naively applying lemma 14 would result in a sequential algorithm which is not in $\mathsf{NC}$. We will next show how we can do the uncrossing in $\mathsf{NC}$.

We will use a divide-and-conquer approach to uncross a given list of tight odd sets $S_{1},\dots,S_{m}$. The high-level description of our procedure, Uncross, is given in algorithm 5. We roughly divide the given sets into two parts, and recursively uncross each part. Then we call the procedure MergeUncross in order to merge the resulting sets.

Next, we will describe the merging procedure MergeUncross. The procedure MergeUncross, similarly to Uncross, accepts a list of tight odd sets and returns a list of pairwise disjoint tight odd sets whose $\Lambda$ is not smaller. With some abuse of notation, we still name the inputs to MergeUncross as $S_{1},\dots,S_{m}$. The difference between MergeUncross and Uncross is that the input sets to MergeUncross satisfy certain properties highlighted below.

Suppose that $\{S_{1},\dots,S_{m}\}=\{R_{1},\dots,R_{p},C_{1},\dots,C_{q}\}$, where $m=p+q$ and $R_{1},\dots,R_{p}$ are pairwise disjoint tight odd sets and $C_{1},\dots,C_{q}$ are also pairwise disjoint tight odd sets. Then $S_{1},\dots,S_{m}$ have no $3$-wise intersections. Furthermore, the intersection graph of $S_{1},\dots,S_{m}$, where two $S_{i}$’s are connected if they have a nonempty intersection, is bipartite.

If we select any three sets $S_{i},S_{j},S_{k}$, then either two of them are from $R_{1},\dots,R_{p}$ or two of them are from $C_{1},\dots,C_{q}$. In either case, those two sets would not have any intersections.

It is also easy to see that the intersection graph is bipartite, since $R_{1},\dots,R_{p}$ naturally form one part and $C_{1},\dots,C_{q}$ the other; by assumption, no two sets from the same part have any intersection. ∎

Having no $3$-way intersections means that we can compute the parity of any union of $S_{1},\dots,S_{m}$ from their pairwise intersections. This is more handily captured by the notion of an intersection parity graph.

For tight odd sets $S_{1},\dots,S_{m}$ satisfying the conditions of lemma 15, define the intersection parity graph $H=(V_{H},E_{H})$, as follows: Let $V_{H}$, the nodes of $H$, be $S_{1},\dots,S_{m}$ and for $i\neq j$ let there be an edge between $S_{i}$ and $S_{j}$ if and only if $\lvert S_{i}\cap S_{j}\rvert$ is odd.