A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
Meena Mahajan, Kasturi Varadarajan · 2000
It has been known for a long time now that the problem of counting the number of perfect matchings in a planar graph is in NC.This result is based on the notion of a pfaffian orientation of a graph.(Recently, Galluccio and Loebl [7] gave a P-time algorithm for the case of graphs of small genus.)However, it is not known if the corresponding search problem, that of finding one perfect matching in a planar graph, is in NC.This situation is intriguing as it seems to contradict our intuition that search should be easier than counting.For the case of planar bipartite graphs, Miller and Naor [22] showed that a perfect matching can indeed be found using an NC algorithm.We present a very different NG-algorithm for this problem.Unlike the Miller-Naor algorithm, our approach directly uses the fact that counting is in NC, and it also generalizes to the problem of finding a perfect matching in a bipartite graph of small (O(log n)) genus.It also rekindles the hope for an NC-algorithm to find a perfect matching in a non-bipartite planar graph.Along the way, we modify the algorithm of Gallucio and Loebl [7] to show that counting the number of perfect matchings in graphs of small genus is in NC.