One of the great things about having new colleagues is the potential new energy, new collaborations, new research directions, and new synergies they bring. Vijay Vazirani, now a Distinguished Professor here at UCI, has brought all four. Vijay has been working on problems related to graph matching for almost 40 years, he tells me, starting with his discovery of the Micali–Vazirani matching algorithm in his first year as a graduate student. Our new preprint, “NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs” (arXiv:1802.00084) continues both that theme and a theme in my own research of graph structure theory.

Parallel algorithms for graph matching were a hot topic in 1988 when Vijay published a paper that became the predecessor to this one, showing that one could count the perfect matchings in \(K_{3,3}\)-minor-free graphs in NC, a complexity class describing parallel algorithms with polylog runtime and polynomially many processors. That may sound somewhat specialized, but this is actually a natural graph class to look at for this problem, because these graphs have Pfaffian orientations allowing their matchings to be counted using matrix determinants, something that’s not true of any graph family that includes \(K_{3,3}\). Earlier, it had been shown by Vijay and others that matchings could be found by randomized parallel algorithms, in all graphs, but finding them deterministically in NC was and is a big open problem. Counting and finding are the same for randomized algorithms, by Vijay’s isolation lemma, but nobody knows how to make that work deterministically. In his paper on \(K_{3,3}\)-free graphs, Vijay posed a special case of this question: can we find matchings in these graphs deterministically?

Since then, parallel algorithms and parallel matching went through a long lull, but now they’re hot again. Derandomized versions of the isolation lemma have led to matching algorithms in QNC (polylog time but with a bigger quasipolynomial number of processors) beginning with the bipartite algorithm of Fenner, Gurjar, and Thierauf at STOC 2016, its generalization to all graphs by Svensson and Tarnawski, and further generalizations by Gurjar, Thierauf, and Vishnoi. Vijay got back into the picture himself, with his new paper with Nima Anari showing that matchings could be found in planar graphs and bounded-genus graphs in NC. Most of this work is so new that I only have arXiv links for it, but I expect it to start appearing in good conferences soon.

Our new paper builds on the planar algorithm of Anari and Vijay, extending it to all one-crossing-minor-free graphs families. “One-crossing-minor-free” means that these are minor-closed graph families in which one of the forbidden minors can be drawn in the plane with only one crossing, as \(K_{3,3}\) can. So our paper solves Vijay’s open question from 1988, but extends well beyond \(K_{3,3}\)-free graphs to many other minor-closed graph families. If you have a planar forbidden minor, you get bounded-treewidth graphs, and the one-crossing-minor-free graph families all have an associated structure theorem in which their graphs can be built by gluing together bounded-treewidth and planar pieces. I’d previously studied flow problems in the same graphs, using the concept of mimicking networks, small networks that you can use to replace the pieces in this decomposition without affecting the overall result. The main idea of the new paper is to define and use a similar concept of mimicking networks for flow instead of matching.

What do we mean by a mimicking network for matching? The idea is that you have a graph \(G\) in which a small set \(T\) of its vertices are designated as “terminals” and the rest are nonterminals. We want to find another graph \(G'\) such that, when any larger graph contains \(G\) and connects to it only through the terminals, we can replace \(G\) by \(G'\) and not affect whether it has a perfect matching. The right definition of this turns out to be that every matching in \(G\) that covers all nonterminals and some terminals corresponds to a matching in \(G'\) that again covers all nonterminals and the same set of terminals, and vice versa. Mimicking networks for flow are easy to construct (find an appropriate family of minimum cuts and merge all subsets of vertices that these cuts do not separate). For matching, we don’t have a similarly explicit construction, only an existence proof that the mimicking networks always have bounded size. But fortunately, we can go through a case analysis to find them all for sets of at most three terminals, which (with a lot of care in the rest of the algorithm) turns out to be all we need. Here they are:

Matching-mimicking networks on up to three terminals

These networks are all outerplanar, which means that we can safely glue them into a triangular face of a planar graph without destroying its planarity, a property our algorithm needs. They also have a subtler property: for each subset of terminals, the matching that covers that subset and all nonterminals is unique. This turns out to be a key step in proving that they can mimic, not just the existence of perfect matchings, but the weights of minimum-weight perfect matchings. We use this property to extend our NC algorithm to the problem of finding minimum-weight perfect matchings in one-crossing-minor-free graphs with polynomially-bounded weights.

Despite solving a 30-year-old open problem, this work raises plenty of new open problems. Chief among them are: how big do matching-mimicking networks need to be, as a function of the number of terminals? Can we construct them explicitly? And is it always possible to mimic the weights of the minimum-weight perfect matching, for larger numbers of terminals than three? So even in this problem area there’s plenty of scope for continued research and collaboration.

(G+)