The Matching Problem in General Graphs is in Quasi-NC

Ola Svensson, Jakub Tarnawski

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 $O({\log }^{3}n)$ time on $n^{O(\log^2 n)}…