The Matching Problem in General Graphs is in Quasi-NC

  • Ola Svensson | School of Computer and Communication Sciences at EPFL, Switzerland

We show that the perfect matching problem in general graphs is in Quasi-NC. That is, we give a deterministic parallel algorithm which runs in polylogarithmic time on quasi-polynomially many processors. The result is obtained by a derandomization of the Isolation Lemma for perfect matchings, which was introduced in the classic paper by Mulmuley, Vazirani and Vazirani to obtain a Randomized NC algorithm.

Our proof extends the framework of Fenner, Gurjar and Thierauf, who proved the analogous result in the special case of bipartite graphs. Compared to that setting, several new ingredients are needed due to the significantly more complex structure of perfect matchings in general graphs. In particular, our proof heavily relies on the laminar structure of the faces of the perfect matching polytope.

This is joint work with Jakub Tarnawski.

Speaker Details

Ola Svensson is a faculty at the School of Computer and Communication Sciences at EPFL, Switzerland. He is interested in theoretical aspects of computer science with an emphasis on the approximability of NP-hard optimization problems. His work on the traveling salesman problem received best paper awards at FOCS’11 and STOC’18 and his work on the perfect matching problem received the best paper award at FOCS’17.

Series: Microsoft Research Talks