NC Algorithms for Perfect Matching and Maximum Flow
in One-Crossing-Minor-Free Graphs

arXiv:1802.00084v1 [] 31 Jan 2018

David Eppstein∗ and Vijay V. Vazirani†
Computer Science Department, University of California, Irvine

Abstract
In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in
K3,3 -minor-free graphs by building on Kasteleyn’s scheme for planar graphs, and stated that this
“opens up the possibility of obtaining an NC algorithm for finding a perfect matching in K3,3 -free
graphs.” In this paper, we finally settle this 30-year-old open problem. Building on the recent
breakthrough result of Anari and Vazirani giving an NC algorithm for finding a perfect matching
in planar graphs and graphs of bounded genus, we also obtain NC algorithms for any minor-closed
graph family that forbids a one-crossing graph. The class contains several well-studied graph
families including the K3,3 -minor-free graphs and K5 -minor-free graphs. Graphs in these classes
not only have unbounded genus, but also can have genus as high as O(n). In particular, we
obtain NC algorithms for:
• Determining whether a one-crossing-minor-free graph has a perfect matching and if so,
finding one.
• Finding a minimum weight perfect matching in a one-crossing-minor-free graph, assuming
that the edge weights are polynomially bounded.
• Finding a maximum st-flow in a one-crossing-minor-free flow network, with arbitrary
capacities.
The main new idea enabling our results is the definition and use of matching-mimicking networks,
small replacement networks that behave the same, with respect to matching problems involving
a fixed set of terminals, as the larger network they replace.

1

Introduction

Obtaining an NC algorithm for matching has been an outstanding open question in theoretical
computer science for over three decades, ever since the discovery of RNC matching algorithms [21,30].
In a recent breakthrough result, Anari and Vazirani gave an NC algorithm for finding a perfect
matching in planar graphs [1]. By using a reduction from flow problems on other surfaces to planar
flow [3], they also extended their result to graphs of bounded genus. Their paper restated the open
problem of obtaining an NC algorithm for finding a perfect matching in K3,3 -minor-free graphs, in
particular because such graphs can have genus as high as O(n). This problem was previously stated
by Vazirani in a paper in which he gave an NC algorithm for computing the number of perfect
matchings in such graphs [36] and stated that this “opens up the possibility of obtaining an NC
algorithm for finding a perfect matching in K3,3 -free graphs.” In this paper, we finally settle this
30-year-old open problem.
∗
†

Supported in part by NSF grants CCF-1618301 and CCF-1616248.
On leave from Georgia Tech.

1

The K3,3 -minor-free graphs are particularly attractive as a target for this problem because they
form a natural extreme case for certain approaches. In particular, they are known to have Pfaffian
orientations, by which their matchings can be counted using matrix determinants [22, 25], while for
K3,3 itself and for any minor-free family that does not forbid it, this tool is unavailable. However,
our result breaks through this barrier: we give an NC algorithm for finding a perfect matching in
graphs belonging to any one-crossing-minor-free class of graphs. That is, if H is any graph that can
be drawn in the plane with only one crossing pair of edges, then we can find perfect matchings in
the H-minor-free graphs in NC. Because K3,3 can be drawn with one crossing, our result includes
in particular the K3,3 -minor-free graphs. More generally, we can find in NC a perfect matching
of minimum weight, in the same families of graphs, when the weights are polynomially-bounded
integers.
In another direction, we obtain an NC algorithm for finding a maximum st-flow in any flow
network whose underlying undirected graph belongs to a one-crossing-minor-free family. This
generalizes Johnson’s 1987 result [19], showing that maximum st-flow in a planar network is in NC.

1.1

Technical ideas

Our main new technical idea is that of a matching-mimicking network. Given a graph G and a set
T of terminal vertices, a matching-mimicking network is a graph G0 , containing T , that has the
same pattern of matchings: every matching of G that covers G \ T corresponds to a matching of G0
that covers G0 \ T and vice versa.
We show that matching-mimicking networks exist for any bounded number of terminals, with a
size bounded by a function of |T |. For |T | ≤ 3, they can be described explicitly; they are planar and
remain planar when glued into the triangular face of a larger planar network, and can be given edge
weights so that their minimum-weight perfect matchings (for each subset of terminals) mimic the
weights of the minimum-weight matchings in the given graph. Both of these properties are needed
by our algorithm.
In the past, mimicking networks for network flow were defined and used by numerous researchers
for obtaining flow algorithms [5, 6, 16, 23, 24]. These mimicking networks were first defined to prove
that maximum flow can be found in NC in graphs of bounded treewidth [16] and later used also
in efficient sequential algorithms for flow in one-crossing-minor-free graphs [5]. Their theoretical
properties have also become an object of study in their own right [6, 23, 24]. It seems likely that,
similarly, our matching-mimicking networks will lead to algorithmic applications beyond our NC
matching algorithm, and additional theory beyond our existence proof.
As with a previous sequential flow algorithm of Chambers and Eppstein [5], we exploit the
structural decomposition of one-crossing-minor-free graphs [32], by repeatedly using mimicking
networks to simplify this structure. However the order in which we perform these replacements must
be more carefully chosen so that our algorithms run in NC. Each step of the replacement process
involves the computation of matchings either in a bounded-treewidth graph or in a planar graph. The
planar matchings can be found by the new result of Anari and Vazirani, and the bounded-treewidth
matchings can be found in NC by using log-space versions of Courcelle’s theorem [9].
Our maximum st-flow result uses a similar algorithmic outline, with flow-mimicking networks
in place of matching-mimicking networks. Our method differs from the sequential algorithm of
Chambers and Eppstein [5], which used flow-mimicking networks on at most three terminals
to replace leaf nodes of the structural decomposition tree. Our matching algorithms, also, use
matching-mimicking networks on at most three terminals, replacing subtrees of more than one
node in a single step. However, our parallel flow algorithm uses flow-mimicking networks for a
second purpose, namely to replace a component of our matching algorithm that involves semiring
2

matrix multiplication. This part of our flow algorithm requires flow-mimicking networks on up to
six terminals.

1.2

History and related results

The first result on the problem of obtaining a fast parallel algorithm for matching was obtained by
Lovasz [26]. In a seminal paper, he proposed a way of computing a perfect matching via methods
quite different from the combinatorial (augmenting-path-finding) methods that were the mainstay
at the time. Using the Tutte matrix of the graph, he proposed methods from linear algebra and
randomization.
When combinatorial methods were found to be lacking for obtaining a fast parallel matching
algorithm, researchers turned to Lovasz’s proposed method. The first RNC algorithm for finding a
perfect matching was obtained by Karp, Upfal, and Wigderson [21]. This was followed by a somewhat
simpler algorithm due to Mulmuley, Vazirani, and Vazirani [30]. Matching has played a central
role in the development of the theory of algorithms, in that its study, from various computational
viewpoints, has led to quintessential paradigms and powerful tools for the entire theory. The two
parallel matching algorithms also led to such gains: the first led to a fundamental understanding of
the computational relationship between search and decision problems [20] and the second yielded a
basic probabilistic technique encapsulated as the Isolation Lemma [30], which has found several
applications in complexity theory and algorithms.
However, this still did not clarify whether randomization was essential for obtaining a fast
parallel matching algorithm. Considering the fundamental insights gained by an algorithmic study
of matching, this 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 [29]. They obtained an NC algorithm
for finding a maximum flow from a set of sources to a set of sinks in a planar network; as a corollary,
they obtained an NC algorithm for finding a perfect matching in bipartite planar graphs. In 2000,
Mahajan and Varadarajan gave an elegant way of using the NC algorithm for counting perfect
matchings to find one, hence giving a different NC algorithm for bipartite planar graphs [28]; as
is well known, Kasteleyn’s algorithm for counting the number of perfect matchings in a planar
graph [22] can be easily made into an NC algorithm for counting matchings by using Csanky’s NC
algorithm for the determinant of a matrix [7].
After a decade and half of lull, there has been a resurgence of activity on this problem in the last
couple of years. In particular, several researchers have obtained quasi-NC algorithms for matching
and its generalizations. Such an algorithm runs in polylogarithmic time; however, it requires
O(1)
n ) processors. All the algorithms in this line of research work by a partial derandomization
O(nlog
of the Isolation Lemma. This line of work was started by Fenner, Gurjar, and Thierauf, who gave a
quasi-NC algorithm for perfect matching in bipartite graphs [12]. Later, Svensson and Tarnawski
extended the result to general graphs [34]. The generalization of bipartite matching to the linear
matroid intersection problem was given by Gurjar and Thierauf [14] and to finding a vertex of a
polytope with totally unimodular constraints by Gurjar, Thierauf, and Vishnoi [15].
A number of new insights into matching were obtained in these works and several of them found
their way, implicitly or explicitly, into the work of [1]. In a similar vein, we believe that results
such as ours, which extend the frontier of NC matching algorithms, are likely to play a critical role
towards the resolution of the full problem.
The first NC algorithm for finding a maximum st-flow in a planar network was obtained by
Johnson [19]. As stated above, this was followed by an NC algorithm for finding a maximum flow
from a set of sources to a set of sinks in a planar network by Miller and Naor [29]. An NC algorithm
for maximum flow in graphs of bounded treewidth was given by Hagerup et al. [16].
3

|T| = 1:

|T| = 2:

Ø:

x

x:

x

Ø:

x

xy:

x

Ø, xy:

x

x:

x

x, y:

x

|T| = 3:

y
y

Ø:

x

y

z

Ø, xy:

x

y

z

Ø, xy, xz:

x

y

z

x

z

xy:

x

y

z

y

xy, xz:

x

y

z

y

xy, xz, yz:

x

y

z

y

x

y

z

x, y:

x

y

z

x, y, z:

y

Ø, xy, xz, yz:

x:

x

y

z

xyz:

x

y

xyz, x:

x

y

z

xyz, x, y:

x

y

z

xyz, x, y, z:

x

y

z

z

Figure 1: Matching-mimicking networks for |T | ≤ 3. In each network, the set T of terminals consists
of the labeled yellow vertices; the remaining non-terminal vertices of the network are the smaller
blue vertices.

2

Matching-Mimicking Networks

A matching, in an undirected graph, is a subset of edges no two of which share an endpoint. The
matching covers a subset of vertices, the ones that are endpoints in the selected edges. If G is a graph
with a specified subset T of vertices, we define the matching pattern of G to be a family of subsets of
T , the subsets X ⊂ T such that some matching of G covers (G\T )∪X (and covers no other vertices).
If G and G0 are two graphs, both containing a shared subset T of vertices, we say that G0 and G0 are
matching-equivalent on T if they have the same matching patterns. A matching-mimicking network
for G and T is any other graph G0 containing T that is matching-equivalent to G on T .
Lemma 1. There is a function f such that any graph G and subset of vertices T has a matchingmimicking network of at most f (|T |) vertices.
Proof. This follows immediately from the fact that T has 2| T | subsets, and therefore that G has
|T |
at most 22 matching patterns. The size of the mimicking network is thus a maximum over a
bounded set and is itself bounded.
This result is not very explicit, and requires us to perform a case analysis to determine the
mimicking network for any matching pattern. It would be of interest to find an explicit algorithm
for constructing a matching-mimicking network of bounded size. In contrast, for flow-mimicking
networks, the following algorithm works: for each nontrivial partition of the terminals, find a
minimum cut in the network that separates the two sides of the partition. Identify two vertices of
the network as equivalent when they are on the same side of every cut, and collapse each equivalence
class to a single vertex.
We have performed the case analysis needed to construct matching-mimicking networks by hand
for |T | ≤ 3, the largest number of terminals needed for our algorithms. The results are depicted in
3
Figure 1. Note that for |T | = 3 the number of matching patterns is 14, not 22 = 256. We achieve
this simplification in the number of cases by combining the following three observations:

4

Figure 2: K5 (left), K3,3 (center), and the eight-vertex Wagner graph (right) are all nonplanar but
can all be drawn in the plane with only one crossing.
• We omit graphs whose matching pattern is empty. If any such graph is detected during our
algorithm for matching, we may abort the algorithm, as the whole graph has no matching.
• The sizes of the subsets of T in any single matching pattern must all have the same parity as
each other.
• We may consider matching patterns to be equivalent whenever one matching pattern can
be obtained from another by permuting the vertices of T . We only need to find matchingmimicking networks for each equivalence class of matching patterns.
The following property indicates that, when glued into a planar graph, all of the matchingmimicking networks of the figure preserve its planarity. We need this property in our algorithm, so
that we can continue to compute matchings in the result of such gluings.
Lemma 2. Let G be a planar graph, let f be a triangular face of a planar drawing of G, and let T
be a subset of the vertices of f . Then the union of G and any of the matching-mimicking networks
of Figure 1, with terminal set T , is another planar graph that can be drawn in the plane with the
matching-mimicking network inside f .
Proof. This follows from the layouts given for these networks in the figure, which are all drawn
outerplanar (planar and with all vertices belonging to the unbounded face of the drawing). Because
they are outerplanar, their unbounded face can be surrounded by triangle f and then, around f ,
the rest of G, without creating any new crossings.

3

Structural Decomposition

A k-clique-sum of two graphs is defined as a graph that can be obtained from the disjoint union of
the two given graphs by identifying a clique of ≤ k vertices in one of the graphs with a clique of the
same size in the other graph, and then optionally deleting some of the edges of the merged clique.
One-crossing-minor-free graphs have a structural decomposition that can be described in terms of
clique-sums: If H is a graph that can be drawn in the plane with at most one edge crossing, then
the H-minor-free graphs can be decomposed by 3-clique-sums into pieces that are either planar or
of bounded treewidth [32]. This decomposition generalizes the result that graphs with a planar
forbidden minor have bounded treewidth, and is a simplified form of the structural decomposition
of arbitrary minor-closed graph families by Robertson and Seymour, which also includes pieces
of bounded genus, apexes (vertices that can be adjacent to any subset of the other vertices in a
single piece), and vortexes (subgraphs of bounded pathwidth attached to a face of a bounded-genus
piece). The graphs with one-crossing drawings include K3,3 and K5 (Figure 2), whose corresponding
minor-free graph classes have even simpler forms of this decomposition: the K3,3 -minor-free graphs
are 2-clique-sums of planar graphs and K5 , and the K5 -minor-free graphs are 3-clique-sums of planar
graphs and the eight-vertex Wagner graph (shown in Figure 2, right).
5

Figure 3: Decomposition of a graph into a 3-clique-sum of simpler pieces (light blue outline) and
cliques (light red outline). The dashed edges indicate edges of glued cliques that are to be removed
after gluing, either because they are redundant (the same edge appears elsewhere) or because they
are not part of the original graph.
We can describe any clique-sum decomposition, such as the decomposition from this structure
theorem, as a two-colored tree (Figure 3), in which the nodes of one color represent pieces (planar
graphs or bounded-treewidth graphs), and the nodes of the other represent cliques on which two are
more pieces are glued. In this tree, the edges of the tree describe the incidence relation between edges
and cliques. Additionally, each clique node of the decomposition tree is labeled with information
describing which of its edges are kept as part of the overall graph. When a planar piece is glued to
other graphs along a non-facial triangle, we may split the planar piece into two smaller pieces on
that triangle; therefore, it is safe to assume that, for each planar piece of the decomposition, the
3-vertex cliques incident to it are all faces of a planar embedding of the piece.
For our algorithms, it is necessary not merely to know that this 3-clique-sum decomposition
exists, but also to find it, in NC. Efficient decomposition algorithms are known for K3,3 -minor-free
graphs and for K5 -minor-free graphs [2, 31], but they are sequential, and we are not aware of such
algorithms for the general case. In previous work on sequential flow algorithms we avoided this issue
by assuming that the decomposition was given as part of the input [5]. Fortunately, in our new
results, we do not need the decomposition to be efficient; it merely needs to be in NC.
A subset of three vertices is a separator if its removal would increase the number of connected
components of the remaining graph. We are interested in finding a decomposition of a given
graph, assumed to be from a one-crossing-minor-free family, by minimal separators of at most three
vertices. However, this decomposition is not unique; for instance K3,3 has two incompatible minimal
separators, the two sides of its bipartition. We define a family of separators to be laminar when no
two vertices from any one separator in the family are separated by any other separator in the family.
There exist graphs (such as the wheel graph) for which there are quadratically many separating
triples, most pairs of which are non-laminar, but maximal laminar sets of separating triples in planar
graphs may be found sequentially in linear time [11]. Our graphs are non-planar, and again we are
only interested in membership in NC.
Lemma 3. We can find a maximal laminar family of separators of size ≤ 3, in any graph, in NC.

6

descendants = 23
rank = 4
descendants = 3
rank = 1

descendants = 8
rank = 3

descendants = 2
rank = 1

descendants = 1
rank = 0

Figure 4: Heavy path decomposition of a rooted tree, showing the number k of descendants of the
top node of each path (including itself) and the rank blog2 kc of the path.
Proof. In parallel, list all subsets of at most three vertices, and check whether each one is a minimal
separator. Create an incomparability graph, in which the vertices represent separators, and the edges
represent non-laminar pairs of separators. Find a maximal independent set in the incomparability
graph. All of the steps of testing whether subsets are minimal separators or whether two separators
are non-laminar involve connectivity computations in undirected graphs, which can be done in NC.
The incomparability graph has polynomial size, and a maximal independent set in any graph can
be constructed in NC [27].
Lemma 4. We can find the structural decomposition of graphs in any one-crossing-minor-free
family, as described above, in NC.
Proof. We find a maximal laminar family of separators of size at most three as above. By performing
additional connectivity computations, we find the pieces that they separate the graph into and the
tree of clique-sums by which these pieces can be glued to form the given graph. Each piece in this
decomposition belongs to the given family (because it is formed by deleting vertices outside the
piece, so it is a minor of the given graph), and itself has no separators of size at most three (by the
assumption that the family of separators that we find is maximal). Therefore, each piece either has
bounded treewidth or is planar.
Additionally we can check which pieces are planar, and find a planar embedding for the planar
pieces, in NC [18].
It will be convenient to define one more tool, a structural decomposition of our structural
decomposition. It is the heavy path decomposition of a tree (the tree describing the structural
decomposition). If any tree T is given an arbitrary root, it may be decomposed into paths by
choosing at each non-leaf node of the tree a single child, the one with the most descendants (counting
each node as one of its own descendants, and choosing arbitrarily in case of ties). The chosen
parent-child edges link together to form a cover of T by vertex-disjoint paths, including some
length-zero paths for unchosen leaf vertices. These paths are the heavy paths of the decomposition.
Each heavy path (other than the one containing the root vertex) has a parent path, the path
containing the parent of the topmost vertex in the path. We may define the rank of a heavy path
whose root has k descendants to be blog2 kc. An example is shown in Figure 4.
Then in a heavy path decomposition of a tree with n nodes, all ranks are integers in the range
from 0 to blog2 nc. If P is any path that does not contain the root, the rank of P is strictly less than
the rank of the parent of P , because P must have at most half as many descendants as its parent (if
it had more, it would have been picked as the heavy child from the parent of the top node of P ). The
heavy path decomposition was introduced for its applications in sequential data structures [17, 33],
and has become a standard tool for graph drawing and geometric graph algorithms [8, 10], but it
7

has also been recently applied in parallel algorithms [13]. By using the Euler tour technique for
trees [35], we may easily count the descendants of each node in a tree, obtaining the following result.
Lemma 5. We may find the heavy path decomposition of any tree, together with the ranks of each
of its paths, in NC.

4

Perfect Matching Algorithm

To find a perfect matching in a given graph G, from a one-crossing-minor-free family F, we perform
the following steps.
1. We apply Lemma 4 to find a decomposition of G into a 3-clique-sum of pieces that are labeled
as either planar or of bounded treewidth.
2. We root the decomposition tree arbitrarily, and use Lemma 5 to find a heavy path decomposition
of the resulting rooted tree structure.
3. For each rank r from 0 to blog2 nc of a path in the heavy path decomposition (sequentially),
we perform the following steps.
(a) In parallel, for each heavy path P of rank r, we replace P in the structural decomposition
of G by a single matching mimicking network. The terminals of this mimicking network
are the (at most three) vertices of G by which P attaches to its parent in the structure
tree, and the graph it mimics is the one formed by the clique-sum of all pieces of the
decomposition of G that either belong to P or descend from P . (We will describe how to
construct this mimicking network below.)
(b) We define a shallow clique of the decomposition to be a node of the rooted decomposition
tree, representing a clique at which two or more pieces are attached to each other, such
that all child pieces are mimicking networks (rather than larger pieces or subtrees), and
such that the parent piece is planar. At each shallow clique, in parallel, we replace the
clique-sum of the attached mimicking networks (a graph of bounded treewidth) with a
single mimicking network for the clique-sum, and then replace the parent piece with its
clique-sum with this mimicking network, removing the shallow clique and its descendants
from the decomposition tree. By Lemma 2 this operation preserves the planarity of the
parent piece. Because we remove the clique from the decomposition tree, it also preserves
the property that in planar pieces of the decomposition, all 3-clique-sums occur on face
triangles.
4. We reverse the sequence of replacements by matching-mimicking networks, maintaining
throughout the reversed sequence a perfect matching for the current graph. When multiple
pieces were replaced in parallel, we perform their reversed replacement in parallel in the same
way. To reverse the replacement of a single graph by a mimicking network, given a matching
in the mimicking network, we construct a corresponding matching in the graph that was
replaced, covering the same terminal vertices and all nonterminal vertices.
It remains to explain how to perform step 3(a), in which we construct the mimicking network
for a heavy path, and also how we maintain enough information about how we constructed it to
reverse the replacement of the path in step 4.

8

Lemma 6. In the algorithm described above, we can compute a mimicking network for each given
heavy path, in NC. Moreover, given a matching in this mimicking network, we can compute a
corresponding matching in the clique-sum of the pieces in the path and its descendants, again in NC.
Proof. At the time our algorithm processes a heavy path P , all heavy paths of lower rank (and in
particular all paths descending from P ) will have already been processed. Therefore, the nodes of P
will be of three types, each associated with a subgraph:
• Planar pieces of the decomposition, possibly with glued-in mimicking networks from lower-rank
paths that preserve the planarity of the piece. We define the subgraph associated with the
node to be this planar piece.
• Bounded-treewidth pieces of the decomposition, possibly attached by clique-sums to mimicking
networks from lower-rank paths. We define the subgraph associated with the node to be
the clique-sum of it and its attached mimicking networks. Because it is a clique-sum of
bounded-treewidth graphs, this associated subgraph has bounded treewidth.
• Cliques of the decomposition, again possibly attached by clique-sums to mimicking networks
from lower-rank paths. As with the bounded-treewidth pieces, we define the subgraph
associated with the node to be the (bounded-treewidth) clique-sum of this clique with its
attached mimicking networks.
For each node interior to P , define the two sides of the node to be the two sets of at most three
vertices by which its subgraph is connected to its neighbors in P . Similarly, for the topmost node of
P (the one closest to the root of the decomposition tree) we let one of the sides be the set of at
most three vertices connecting it to its parent, and for the bottommost (leaf) node of P we define
one of its sides to be the empty set.
Then the matchings that are possible for the subgraph associated with each node can be
summarized by a Boolean matrix, the transfer matrix of the node. The rows of the matrix are
indexed by subsets of the vertices on one side of the node, the side closest to the leaf of the path,
and the columns of the matrix are indexed by subsets of the vertices on the other side. We set the
entry of this matrix in row i and column j to be true if there exists a matching of the subgraph
associated with the node that covers all interior (non-side) vertices of the subgraph, and covers the
subsets of the two sides indexed by i and j. Taking into account the fact that, at each side of each
node, the subsets of vertices that can be matched are constrained to all have the same parity, these
matrices have dimension at most 4 × 4, but are in some cases smaller. For instance, the transfer
matrix of the leaf node of the path has only one row, corresponding to the empty set, as its set of
vertices on the leaf side is the empty set. Each Boolean value in each of these transfer matrices can
be found in parallel by testing for the existence of a perfect matching in the induced subgraph of
the vertices that should be covered.
The transfer matrix for the clique-sum of any contiguous subsequence of nodes in the path is
just the product of its matrices, over the Boolean (∨, ∧) semiring, in left-to-right order from the
leaf end to the root end. As with any product of matrices, we can compute the product matrix in
NC, for instance by associating the nodes of the subsequence with the leaves of a balanced binary
tree and, at each interior node of the binary tree, multiplying the matrices from the two child nodes.
Because the rightmost (leaf) matrix is a row vector, the product of all the matrices will also be a
row vector, indicating which subsets of the three vertices on the top side of the top node of P can
be covered by a matching that also covers all vertices belonging to the subgraphs associated with P .
The information in this row vector is exactly what we need to compute a mimicking network for P .

9

To make this process reversible, whenever we compute the product of two transfer matrices we
also store, for each true Boolean value in the product matrix, a pair of true Boolean values in the
two multiplicands that cause that product value to be true (choosing arbitrarily when multiple pairs
would cause it to be true). Then, when we have chosen a matching in the mimicking network for P
and wish to replace it by a matching in the subgraphs associated with P , we trace back through this
stored information to find a sequence of true Boolean values in the transfer matrices of each node of
P that together correspond to a matching of the correct type. Then, in each subgraph associated
with a node of P , we perform a matching algorithm to find a single matching corresponding to the
position of this value in its transfer matrix.
Theorem 7. We can find a perfect matching in any graph from a one-crossing-minor-minimal
graph family, in NC.
Proof. All mimicking networks used to replace other pieces in the decomposition tree have bounded
size, and therefore bounded treewidth. When we merge a shallow clique into its parent in the
decomposition tree, we are gluing a single mimicking network for at most three terminals into a
vertex, edge, or triangle of the parent graph. We only perform this merge step once per vertex, edge,
or triangle of the parent piece. The parent piece must have been planar before the gluing step, and
by Lemma 2 it remains planar. Correspondingly, because this gluing step performs a 3-clique-sum of
a graph of bounded treewidth, if the parent piece was of bounded treewidth before the gluing step,
it remains of bounded treewidth. Thus, all the replacements performed by the algorithm preserve
the structure of the decomposition, allowing the algorithm to continue correctly in later steps.
There are logarithmically many iterations of the outer loop, and each iteration performs only
steps that can be performed in NC. Therefore, the overall algorithm is also in NC.

5

Minimum Weight Perfect Matching Algorithm

Our algorithm for finding minimum-weight matchings in one-crossing-minor-free graphs is similar in
outline to the algorithm for unweighted matchings. We find a decomposition tree and its heavy path
decomposition, and then for each path in rank order replace it by a mimicking network. However,
to apply this method to minimum-weight perfect matching, we need three additional ingredients:
• When we compute transfer matrices and their products, we replace the Boolean values in
these matrices by numerical values, the minimum weight of each matching, and we replace the
(∨, ∧) semiring used for existence of a matching with the (min, +) semiring to compute the
minimum weight of a matching. As before, whenever we multiply two of these matrices we
store for each entry of the product the pair of entries of the multiplicands that gave rise to its
value.
• We need to be able to construct minimum-weight perfect matchings in the pieces of the
structural decomposition, namely planar graphs and graphs of bounded treewidth. For planar
graphs a minimum-weight perfect matching algorithm in NC (restricted to polynomiallybounded integer weights) was given by Anari and Vazirani [1]. For bounded treewidth graphs
it appears that the log-space version of Courcelle’s theorem [9] does not support optimization
of structures expressible in monadic second-order logic, so it does not directly provide an
algorithm for minimum-weight perfect matching in bounded-treewidth graphs. Nevertheless
it is straightforward to obtain an NC algorithm for this problem directly, for instance by
combining the known log-space tree-decomposition algorithm (which can be interpreted as
decomposing any graph of bounded treewidth into a clique-sum of pieces of bounded size)
10

with our method of heavy path decomposition and multiplication of transfer matrices along
each heavy path.
• We need planarity-preserving weighted matching-mimicking networks for sets of at most three
terminals. We detail this ingredient below.
In order for a matching-mimicking network to preserve the choice of which perfect matching has
minimum weight, we will require it to have the following property: let M and M 0 be two matchings
in the original network that we wish to mimic, each covering all nonterminals and a different subset
of terminals, and each of minimum weight for the subset of terminals that it covers. Then the
difference in weights between M and M 0 should be the same as the difference in weights between
the corresponding two minimum-weight matchings in the mimicking network. We do not require
M or M 0 to have the same weight in the mimicking network as in the original network, but only
that the two matchings differ by the same amount. This is because some of the matchings in our
mimicking networks have an empty set of matched edges, and we cannot control the total weight of
the empty set.
If a mimicking network had two different matchings covering the same subsets of terminals, we
would have to worry about which of these two is the minimum-weight matching. Fortunately, this is
not an issue:
Observation 8. For all of the three-terminal mimicking networks of Figure 1, and all matchable
subsets of terminals in each network, there is exactly one matching that covers that subset of
terminals and all nonterminals.
This uniqueness property is clearly true when the mimicking network is a tree (for every leaf
nonterminal must be matched and, regardless of whether we specify to match or not match a leaf
terminal, there is only one way to do it. Therefore, the observation can be proven by a short case
analysis of the remaining two mimicking networks containing cycles.
Lemma 9. For each of the three-terminal mimicking networks of Figure 1, it is possible to set
weights on the edges of the network to preserve any given assignment of differences to the weights of
its matchings.
Proof. When any of the matchings in one of these networks has an edge e that is not used in
any other of the matchings, we can set the weights of its other edges recursively, and then choose
a weight for e that causes its matching to have the correct difference with the other matchings.
Using this strategy we can handle all of the mimicking networks in Figure 1 that have at most two
matchings (because surely each of the two has a uniquely used edge) or that have no non-terminals
(because in these networks, every non-empty matching is disjoint). The remaining cases are:
• The network for the matching pattern {xy, xz, yz}. In this network, the two edges incident to
y in the figure are uniquely used in their two matchings.
• The network for the matching pattern {xyz, x, y}. In this network, the three matchings are
disjoint, so all edges are uniquely used.
• The network for the matching pattern {xyz, x, y, z}. In this network, the triangle of edges
connecting x, y, and the nonterminal vertex are uniquely used in their matchings.
Therefore, in all cases we can use the same three-terminal planarity-preserving matchingmimicking networks as in the unweighted case. These are all the ingredients that we need to prove
the following result:
Theorem 10. We can find a minimum-weight perfect matching in any graph from a one-crossingminor-minimal graph family, with polynomially-bounded weights, in NC.
11

6

Maximum Flow Algorithm

A similar algorithmic outline can be used to find a maximum st-flow in directed flow networks whose
underlying undirected graphs belong to a one-crossing-minor-free graph family. The differences are
the following:
• We use the flow mimicking networks of Hagerup et al [16], and the three-terminal planaritypreserving flow mimicking networks of Chambers and Eppstein [5], in place of our new
matching-mimicking networks.
• We use the same structural decomposition of the given flow network as we used in our
matching algorithm, but we modify its heavy path decomposition. We define the root the
structural decomposition tree to be the entire path between the piece containing s and the
piece containing t (where s and t are the two flow terminals). Based on this choice of root, we
perform a heavy path decomposition of the remaining parts of the tree in the same way as
before. Finally, we include the root path as a path in the decomposition, and we assign it a
rank greater than that of any other path in the decomposition. In this way, the algorithm will
simplify all other paths in the graph before reaching the root path.
• When processing any single path in the heavy path decomposition, we have no way of using
matrices to represent the flows through a subgraph associated with a node of the path. Instead,
we represent these flows with flow mimicking networks for at most six terminals, treating the
vertices on both sides of each node as terminals. Instead of using matrix multiplication in a
semiring to combine pairs of matrices, we combine pairs of mimicking networks by constructing
a single mimicking network for their union.
• In the root path of the decomposition, the two end nodes of the path are the ones containing
the terminals s and t. Rather than defining one side of these nodes to be the empty set, we
use the sets {s} and {t} respectively. Alternatively, when the root path consists of a single
node whose associated subgraph contains both s and t, we use these two sets as its two sides.
In this way, the mimicking network constructed for this root path will consist of a single
capacitated edge from s to t, in which finding a maximum flow is trivial.
Hence we have the following result:
Theorem 11. We can find a maximum flow from s to t in any flow network in a one-crossingminor-minimal graph family, with source s and sink t, in NC.

7

Discussion and Open Problems

We conclude with some open problems that result from our work:
• Can we prove an explicit upper bound on the size of matching-mimicking networks, as a
function of the number of terminals? Do weighted matching-mimicking networks exist for
arbitrary numbers of terminals?
• Because Anari and Vazirani [1] show how to find perfect matchings in bounded-genus graphs,
our method immediately extends to facial 3-clique-sums of bounded-genus graphs and boundedtreewidth graphs. However, it is not clear what happens when bounded-genus pieces are glued
by clique-sums on triangles that are not faces. Do the facial 3-clique-sums of bounded-genus
graphs and bounded-treewidth graphs include any other natural graph classes?
12

• Is it possible to use the structure theorem for more general minor-closed graph families, allowing
non-facial clique-sums, apexes, and vortexes, to find perfect matchings in such families in NC?
• Chambers and Eppstein [5] used mimicking networks to find near-linear-time sequential
maximum flow algorithms for one-crossing-minor-free graphs. Our matching-mimicking
networks could also be applied in finding sequential perfect matching algorithms for the same
class of graphs. However, in order to obtain a speedup with this method, we need a subroutine
for fast perfect matching in planar graphs. It is known that perfect matching in bipartite
planar graphs can be solved in near-linear-time, by a reduction to flow with multiple sources
and multiple sinks [4]. Are there similarly fast algorithms for non-bipartite planar perfect
matching?

References
[1] Nima Anari and Vijay V. Vazirani, Planar graph perfect matching is in NC, Electronic preprint
arxiv:1709.07822, 2017.
[2] Takao Asano, An approach to the subgraph homeomorphism problem, Theoretical Computer
Science 38 (1985), no. 2–3, 249–267, doi:10.1016/0304-3975(85)90222-1, MR 0807925.
[3] Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen, All-pairs
minimum cuts in near-linear time for surface-embedded graphs, Proc. 32nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, Schloss
Dagstuhl, 2016, pp. 22:1–22:16, arXiv:1411.7055, doi:10.4230/LIPIcs.SoCG.2016.22, MR
3540865.
[4] Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen,
Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time, SIAM
J. Comput. 46 (2017), no. 4, 1280–1303, arXiv:1105.2228, doi:10.1137/15M1042929, MR
3681377.
[5] Erin Wolf Chambers and David Eppstein, Flows in one-crossing-minor-free graphs, J. Graph Algorithms and Applications 17 (2013), no. 3, 201–220, doi:10.7155/jgaa.00291, MR 3043209.
[6] S. Chaudhuri, K. V. Subrahmanyam, F. Wagner, and C. D. Zaroliagis, Computing mimicking
networks, Algorithmica 26 (2000), no. 1, 31–49, Graph algorithms and applications (Dagstuhl,
1996), doi:10.1007/s004539910003, MR 1730966.
[7] L. Csanky, Fast parallel matrix inversion algorithms, SIAM J. Comput. 5 (1976), no. 4, 618–623,
doi:10.1137/0205040, MR 0455310.
[8] Christian A. Duncan, David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, and Martin
Nöllenburg, Drawing trees with perfect angular resolution and polynomial area, Discrete Comput.
Geom. 49 (2013), no. 2, 157–182, doi:10.1007/s00454-012-9472-y, MR 3017904.
[9] Michael Elberfeld, Andreas Jakoby, and Till Tantau, Logspace versions of the theorems of
Bodlaender and Courcelle, Proc. 51st IEEE Symp. Foundations of Computer Science (FOCS
2010), 2010, pp. 143–152, doi:10.1109/FOCS.2010.21, MR 3024788.
[10] David Eppstein and Michael T. Goodrich, Succinct greedy geometric routing using hyperbolic
geometry, IEEE Trans. Comput. 60 (2011), no. 11, 1571–1580, doi:10.1109/TC.2010.257,
MR 2830035.
13

[11] David Eppstein and Bruce Reed, Finding maximal sets of laminar 3-separators in planar graphs
in linear time, Manuscript, 2018.
[12] Stephen Fenner, Rohit Gurjar, and Thomas Thierauf, Bipartite perfect matching is in quasi-NC,
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, ACM,
2016, pp. 754–763, arXiv:1601.06319, doi:10.1145/2897518.2897564, MR 3536611.
[13] Johannes Fischer, Dominik Köppl, and Florian Kurpicz, On the benefit of merging suffix array
intervals for parallel pattern matching, 27th Annual Symposium on Combinatorial Pattern
Matching, CPM 2016, June 27-29, 2016, Tel Aviv, Israel (Roberto Grossi and Moshe Lewenstein,
eds.), Leibniz International Proceedings in Informatics (LIPIcs), vol. 54, Schloss Dagstuhl,
2016, pp. 26:1–26:11, doi:10.4230/LIPIcs.CPM.2016.26, MR 3539183.
[14] Rohit Gurjar and Thomas Thierauf, Linear matroid intersection is in quasi-NC, Proceedings of
the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2017, pp. 821–830,
doi:10.1145/3055399.3055440, MR 3678231.
[15] Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi, Isolating a vertex via lattices:
Polytopes with totally unimodular faces, Electronic preprint arxiv:1708.02222, 2017.
[16] Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde, Characterizing
multiterminal flow networks and computing flows in networks of small treewidth, J. Computer
and System Sciences 57 (1998), no. 3, 366–375, 14th ACM SIGACT-SIGMOD-SIGART
Symposium on Principles of Database Systems (San Jose, CA, 1995), doi:10.1006/jcss.1998.
1592, MR 1668023.
[17] Dov Harel and Robert E. Tarjan, Fast algorithms for finding nearest common ancestors, SIAM
J. Comput. 13 (1984), no. 2, 338–355, doi:10.1137/0213024, MR 0739994.
[18] Joseph Ja’Ja’ and Janos Simon, Parallel algorithms in graph theory: planarity testing, SIAM J.
Comput. 11 (1982), no. 2, 314–328, doi:10.1137/0211024, MR 652905.
[19] Donald B. Johnson, Parallel algorithms for minimum cuts and maximum flows in planar
networks, J. ACM 34 (1987), no. 4, 950–967, doi:10.1145/31846.31849, MR 913849.
[20] Richard M. Karp, Eli Upfal, and Avi Wigderson, Are search and decision programs computationally equivalent?, Proceedings of the Seventeenth Annual ACM Symposium on Theory of
computing, ACM, 1985, pp. 464–475, doi:10.1145/22145.22197.
[21]

, Constructing a perfect matching is in random NC, Combinatorica 6 (1986), no. 1,
35–48, doi:10.1007/BF02579407, MR 0856642.

[22] P. W. Kasteleyn, Graph theory and crystal physics, Graph Theory and Theoretical Physics,
Academic Press, London, 1967, pp. 43–110, MR 0253689.
[23] Arindam Khan and Prasad Raghavendra, On mimicking networks representing minimum
terminal cuts, Information Processing Letters 114 (2014), no. 7, 365–371, doi:10.1016/j.ipl.
2014.02.011, MR 3180757.
[24] Robert Krauthgamer and Inbal Rika, Mimicking networks and succinct representations of
terminal cuts, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA ’12) (Philadelphia, PA), SIAM, 2012, pp. 1789–1799, doi:10.1137/1.9781611973105.
128, MR 3203013.
14

[25] Charles H. C. Little, An extension of Kasteleyn’s method of enumerating the 1-factors of
planar graphs, Combinatorial Mathematics (Proc. Second Australian Conf., Univ. Melbourne,
Melbourne, 1973) (Berlin), Lecture Notes in Mathematics, vol. 403, Springer, 1974, pp. 63–72,
doi:10.1007/BFb0057377, MR 0382062.
[26] L. Lovász, On determinants, matchings, and random algorithms, Fundamentals of computation theory (Proc. Conf. Algebraic, Arith. and Categorical Methods in Comput. Theory,
Berlin/Wendisch-Rietz, 1979), Math. Res., vol. 2, Akademie-Verlag, Berlin, 1979, pp. 565–574,
MR 563723.
[27] Michael Luby, A simple parallel algorithm for the maximal independent set problem, SIAM J.
Comput. 15 (1986), no. 4, 1036–1053, doi:10.1137/0215074, MR 861369.
[28] Meena Mahajan and Kasturi R. Varadarajan, A new NC-algorithm for finding a perfect matching
in bipartite planar and small genus graphs, Proceedings of the Thirty-second Annual ACM
Symposium on Theory of Computing, ACM, 2000, pp. 351–357, doi:10.1145/335305.335346,
MR 2114550.
[29] Gary L. Miller and Joseph Naor, Flow in planar graphs with multiple sources and sinks, SIAM
J. Comput. 24 (1995), no. 5, 1002–1017, doi:10.1137/S0097539789162997, MR 1350755.
[30] Ketan Mulmuley, Umesh V. Vazirani, and Vijay V. Vazirani, Matching is as easy as matrix
inversion, Combinatorica 7 (1987), no. 1, 105–113, doi:10.1007/BF02579206, MR 905157.
[31] Bruce Reed and Zhentao Li, Optimization and recognition for K5 -minor free graphs in linear
time, Proc. 8th Latin American Theoretical Informatics Symposium (LATIN 2008) (Berlin),
Lecture Notes in Computer Science, vol. 4957, Springer, 2008, pp. 206–215, doi:10.1007/
978-3-540-78773-0_18, MR 2472737.
[32] Neil Robertson and Paul Seymour, Excluding a graph with one crossing, Graph structure theory
(Seattle, WA, 1991), Contemp. Math., vol. 147, American Mathematical Society, Providence,
RI, 1993, pp. 669–675, doi:10.1090/conm/147/01206, MR 1224738.
[33] Daniel D. Sleator and Robert E. Tarjan, A data structure for dynamic trees, J. Computer
and System Sciences 26 (1983), no. 3, 362–391, doi:10.1016/0022-0000(83)90006-5, MR
710253.
[34] Ola Svensson and Jakub Tarnawski, The matching problem in general graphs is in quasi-NC,
Electronic preprint arxiv:1704.01929, 2017.
[35] Robert E. Tarjan and Uzi Vishkin, An efficient parallel biconnectivity algorithm, SIAM J.
Comput. 14 (1985), no. 4, 862–874, doi:10.1137/0214061, MR 0807887.
[36] Vijay V. Vazirani, NC algorithms for computing the number of perfect matchings in K3,3 -free
graphs and related problems, Information and Computation 80 (1989), no. 2, 152–164, (a
preliminary version of this paper appeared in Proc. First Scandinavian Workshop on Algorithm
Theory (1988), 233-242), doi:10.1016/0890-5401(89)90017-5, MR 980123.

15

