lemmatheorem lemma observationtheorem observation

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

David Eppstein and Vijay V. Vazirani
Computer Science Department, University of California, Irvine Supported in
part by NSF grants CCF-1618301 and CCF-1616248.On leave from Georgia Tech.

###### Abstract

In 1988, Vazirani gave an NC algorithm for computing the number of perfect
matchings in $K_{3,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 $K_{3,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
$K_{3,3}$-minor-free graphs and $K_{5}$-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 $K_{3,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 $K_{3,3}$-free graphs.” In this paper, we finally settle
this 30-year-old open problem.

The $K_{3,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
$K_{3,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 $K_{3,3}$ can be
drawn with one crossing, our result includes in particular the
$K_{3,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 $G^{\prime}$, containing $T$, that has the same pattern of matchings:
every matching of $G$ that covers $G\setminus T$ corresponds to a matching of
$G^{\prime}$ that covers $G^{\prime}\setminus 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|\leq 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 [16, 6, 24, 5, 23]. 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, 24, 23]. 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 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(n^{\log^{O(1)}n})$ processors. All the algorithms in this line of research
work by a partial derandomization 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].

##  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\subset T$ such that some matching of $G$ covers
$(G\setminus T)\cup X$ (and covers no other vertices). If $G$ and $G^{\prime}$
are two graphs, both containing a shared subset $T$ of vertices, we say that
$G^{\prime}$ and $G^{\prime}$ are _matching-equivalent_ on $T$ if they have
the same matching patterns. A _matching-mimicking network_ for $G$ and $T$ is
any other graph $G^{\prime}$ containing $T$ that is matching-equivalent to $G$
on $T$.

######  Lemma .

There is a function $f$ such that any graph $G$ and subset of vertices $T$ has
a matching-mimicking 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 at most $2^{2^{|T|}}$ matching patterns. The size of
the mimicking network is thus a maximum over a bounded set and is itself
bounded. ∎

Figure 1: Matching-mimicking networks for $|T|\leq 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.

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|\leq 3$, the largest number of terminals needed for
our algorithms. The results are depicted in Figure 1. Note that for $|T|=3$
the number of matching patterns is 14, not $2^{2^{3}}=256$. We achieve this
simplification in the number of cases by combining the following three
observations:

  * •

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 matching-mimicking networks for each equivalence class of
matching patterns.

The following property indicates that, when glued into a planar graph, all of
the matching-mimicking 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 .

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

Figure 2: $K_{5}$ (left), $K_{3,3}$ (center), and the eight-vertex Wagner
graph (right) are all nonplanar but can all be drawn in the plane with only
one crossing.

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 $\leq 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 $K_{3,3}$ and
$K_{5}$ (Figure 2), whose corresponding minor-free graph classes have even
simpler forms of this decomposition: the $K_{3,3}$-minor-free graphs are
$2$-clique-sums of planar graphs and $K_{5}$, and the $K_{5}$-minor-free
graphs are $3$-clique-sums of planar graphs and the eight-vertex Wagner graph
(shown in Figure 2, right).

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.

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.

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 $K_{3,3}$-minor-free graphs and for $K_{5}$-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 $K_{3,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 .

We can find a maximal laminar family of separators of size $\leq 3$, in any
graph, in NC.

###### 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 .

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].

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
$\lfloor\log_{2}k\rfloor$ of the path.

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
$\lfloor\log_{2}k\rfloor$. 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 $\lfloor\log_{2}n\rfloor$. 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 [33, 17], and has become a standard tool for graph drawing and
geometric graph algorithms [8, 10], but it 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 .

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 $\mathcal{F}$, we perform the following steps.

  1. 1.

We apply section 3 to find a decomposition of $G$ into a 3-clique-sum of
pieces that are labeled as either planar or of bounded treewidth.

  2. 2.

We root the decomposition tree arbitrarily, and use section 3 to find a heavy
path decomposition of the resulting rooted tree structure.

  3. 3.

For each rank $r$ from $0$ to $\lfloor\log_{2}n\rfloor$ of a path in the heavy
path decomposition (sequentially), we perform the following steps.

    1. (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.)

    2. (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 section 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. 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.

######  Lemma .

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\times 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
$(\vee,\wedge)$ 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$.

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 1.

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 section 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 $(\vee,\wedge)$ 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 polynomially-bounded 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) 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^{\prime}$ 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^{\prime}$ 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^{\prime}$ 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 .

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 .

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 matching-mimicking networks as in the unweighted case. These are
all the ingredients that we need to prove the following result:

######  Theorem 2.

We can find a minimum-weight perfect matching in any graph from a one-
crossing-minor-minimal graph family, with polynomially-bounded weights, in NC.

##  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 planarity-preserving 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 3.

We can find a maximum flow from $s$ to $t$ in any flow network in a one-
crossing-minor-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 bounded-treewidth 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?

  * •

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 Nö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.
  * [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 Kö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.
  * [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. Lová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 $K_{5}$-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 $K_{3,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.