Maximum matching in graphs with an excluded minor
Raphael Yuster, Uri Zwick · 2007
Abstract We present a new randomized algorithm for findinga maximum matching in H-minor free graphs. Forevery fixed H, our algorithm runs in O(n3!/(!+3)) < O(n1.326) time, where n is the number of verticesof the input graph and! < 2.376 is the exponentof matrix multiplication. This improves upon the previous O(n1.5) time bound obtained by applying the O(mn1/2)-time algorithm of Micali and Vazirani on thisimportant class of graphs. For graphs with bounded genus, which are spe-cial cases of H-minor free graphs, we present a ran-domized algorithm for finding a maximum matching in O(n!/2) < O(n1.19) time. This extends a previous ran-domized algorithm of Mucha and Sankowski, having the same running time, that finds a maximum matching ina planar graphs. We also present a deterministic algorithm with arunning time of O(n1+!/2) < O(n2.19) for counting thenumber of perfect matchings in graphs with bounded genus. This algorithm combines the techniques usedby the algorithms above with the counting technique of Kasteleyn. Using this algorithm we can also count,within the same running time, the number of T-joinsin planar graphs. As special cases, we get algorithms for counting Eulerian subgraphs (T = OE) and oddsubgraphs ( T = V) of planar graphs. 1 Introduction A matching in a graph is a set of pairwise disjointedges. A perfect matching in a graph with n verticesis a matching of size n/2, and a maximum matchingis a matching of largest possible size. The problems