Sunday, October 08, 2017

Planar Matching in NC

There are problems that I carry in my bones, even if I am not actively working on them. Every once in a while you are working on something that reminds you of these problems and try to renew the attack, other times they simply simmer in your psyche.

One such problem is perfect matching in NC. I teach the Mulmuley, Vazirani, Vazirani result that perfect matching is in RNC, and even recently went back to the open problem of producing a NC solution when I was looking at some MapReduce variants.

Vijay and Nina have an arXiv paper showing planar graph perfect matching is in NC and I am looking forward to reading it. 



Blogger Sasho said...

Ola Svensson reminded me yesterday of a beautiful related open problem: given a graph with edges colored red or blue, decide in deterministic polynomial time whether it has a perfect matching with exactly k red edges.

10:37 PM  

Post a Comment

<< Home