Deterministic Parallel algorithm for perfect matching in general graphs?

Question

In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. And there are problems BELIEVED to be in $\mathsf{NC}$, but a proof is not found yet.

Perfect Matching problem is one of the most fundamental problem raised in graph theory: given a graph $G$, we have to find a perfect matching for $G$. As I could found on the internet, despite of the beautiful polynomial time Blossom algorithm by Edmonds, and a RANDOMIZED parallel algorithm by Karp, Upfal and Wigderson in 1986, only a few subclasses of graphs are known to have $\mathsf{NC}$ algorithms.

In Jan. 2005 there's a post in the blog Computational Complexity that claims it remains open whether Perfect Matching is in $\mathsf{NC}$. My question is:

Is there any progress since then, beyond the randomized $\mathsf{NC}$ algorithm?

To clarify my interest, any algorithm which deals with GENERAL graphs are nice. Although algorithms for subclasses of graphs are OK too, that may be not on my attentions. Thank you all!

---

EDIT at 12/27:

Thank you for all your help, I try to summarize all the results in one figure:

The lowest known classes contain the following problems:

• Matching in general graphs: $\mathsf{RNC}$ [KUW86], $\mathsf{RNC}^2$ [CRS93]
• Matching in bipartite planar/constant genus graphs: $\mathsf{UL}$/$\mathsf{SPL}$ [DKT10]/[DKTV10]
• Matching when the total number is polynomial: $\mathsf{SPL}$ [H09]
• Lex-first maximal matching: $\mathsf{CC}$ [MS89]

Furthermore, under plausible complexity assumption: $\mathsf{SPACE[n]}$ requires exponential circuits, Matching in general graphs is in $\mathsf{SPL}$ [ARZ98].

Answer 1

$NC$ algorithms for perfect matchings in general graphs is still open but there has been some progress. Here are a few that I am aware of:

For general graphs, Agrawal-Hoang-Thierauf showed that given the promise that the number of perfect matchings is small, there is an $NC^2$ algorithm to enumerate all of them.

For the class of planar graphs, the pfaffian plays a big role. Kastelyn showed how every planar graph can be oriented in a way such that the pfaffian exactly equals the number of perfect matchings. (This was used by Valiant in to give "Holographic algorithms" for various problems) Mahajan-Subramanya-Vinay showed how the pfaffian can be computed in $NC$ using modifications of clow sequences. (Kastelyn in fact gives an algorithm to find the embedding in $P$ but I'm not sure if the pfaffian embedding can also be computed in $NC$; if yes, that would mean that counting perfect matchings in planar graphs is in $NC$.)

And a recent result of Vinodchandran-Tewari show that the isolation lemma can be "derandomized" for planar graphs (using Green's theorem!) to put planar reachability in $UL$. But $NC$ algorithms for planar matchings are still open (thanks to Raghunath for correcting my claim that it is in $UL$). An $NC$ algorithm for bipartite planar matchings was given by Datta-Kulkarni-Roy

Hope this helps.

Answer 2

A few years later :) and Perfect Matching is now known to be in Quasi-NC (that is, you need quasi-polynomially many processors). See the paper of Fenner, Gurjar and Thierauf (for bipartite graphs) https://arxiv.org/pdf/1601.06319.pdf and our work with Ola Svensson (for general graphs): https://arxiv.org/pdf/1704.01929

Answer 3

The derandomization of isolation lemma by Tewari-Vinodchandran does not give a UL upper bound on planar matching unfortunately. In fact I dont even think an NC algorithm is not known for planar matching. But in a recent work with Datta, Kulkarni and Nimbhorkar we show an UL upper bound on bipartite planar matching (the writeup of this result is still in progress). This is interesting because prior to this even an NL bound was not known for this problem.

Answer 4

When an optimization problem is known to be hard, it is usual to look at their maximal versions. For example, whereas independent set is NP-Complete, the lex first maximal independent set, which is P-Complete.

In the same vein, while we do not know the exact complexity of Perfect Matching, the lex first maximal matching has been studied and is know to be CC-complete (CC stands for problems that can be solved by polynomial size comparator circuits). It turns out that the best known parallel solution of this class has $\sqrt n$ depth. Much of all this should be found in this paper by Mayr, Subramanian.

All this points says that there may not be an easily parallelizable NC version for this. But then who knows? Someone may derandomize the RNC version next week!

Edit: Thanks Ramprasad. But here is another link to the paper.

Answer 5

Parallel approximation results may shed light on the parallel complexity of perfect matching. Fischer, Goldberg, Haglin, and Plotkin designed parallel algorithm to find approximate $(1-\epsilon)-$maximum cardinality matching which puts the approximation problem in $NC$. Their algorithm uses $n^{\Theta(1/\epsilon)}$ processors and runs in $O(\log^3 n)$ time.

T. Fischer, A. V. Goldberg, D. J. Haglin, and S. Plotkin. Approximating matchings in parallel. Info. Proc. Lett., 46(3):115, 1993