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

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.