Planar Graph Perfect Matching is in NC

Is finding a perfect matching in NC? That is, is there an efficient deterministic parallel graph for it? This has been a long outstanding question for over three decades, ever since the discovery of the RNC matching algorithm. Finding a matching on general graph is much easier than counting the number of perfect matchings. However, on planar graph, it has been long known that counting the number of perfect matching is in NC but whether there is an NC algorithm that finds one has remained open. In this seminar, I will talk about a paper uploaded last week by Anari and Vazirani, which give a first NC algorithm for finding a perfect matching.