Title: NC algorithm to find perfect matching in planar graphs
| Speaker: | Prashant Gokhale |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
Abstract: Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution.
Partial progress towards this question was made by Mahajan and Varadarajan in 2000 (and independently using a different technique by Miller and Naor in 1989) in the case of planar bipartite graphs, by elegantly using an NC algorithm to count perfect matchings to find one by repeatedly moving to lower dimensional faces in the perfect matching polytope. I will start by first talking about this algorithm.
A major breakthrough in this line of work was made by Anari and Vazirani in 2018 which provided a NC algorithm for general planar graphs. Several new ideas are needed to circumvent difficulties which arise in non-bipartite planar graphs. I will attempt to explain the key ideas behind this algorithm, and (time permitting) argue why they work.