<p>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) <a href="https://arxiv.org/pdf/1601.06319.pdf" rel="noreferrer">https://arxiv.org/pdf/1601.06319.pdf</a> and our work with Ola Svensson (for general graphs): <a href="https://arxiv.org/pdf/1704.01929" rel="noreferrer">https://arxiv.org/pdf/1704.01929</a></p>

CC BY-SA 3.0
2017-04-11T11:28:38.983Z
2017-04-11T11:28:38.983Z
Jakub Tarnawski
<p>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.</p>

CC BY-SA 2.5
2010-11-15T18:22:19.547Z
Welcome to TCS Stack Exchange!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-27T01:37:17.760Z
Now I found [the paper](http://www.eccc.uni-trier.de/report/2010/201/download) by Datta, Kulkarni and you. I'll read it asap, Thank you!!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-15T16:52:44.847Z
2010-11-15T16:52:44.847Z
Raghunath Tewari
<p>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.</p>

<p>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 <a href="http://ieeexplore.ieee.org/iel2/250/1606/00041817.pdf" rel="nofollow">this paper by Mayr, Subramanian.</a> </p>

<p>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!</p>

<p><b>Edit:</b> Thanks Ramprasad. But here is another link to the <a href="http://bit.ly/d5jJcT" rel="nofollow">paper.</a></p>

CC BY-SA 2.5
2010-11-15T11:25:41.977Z
Oops, I have no account to access the paper. What is the title of it?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-15T12:02:02.393Z
"The complexity of circuit value and network stability". I've put a copy of the paper here: http://www.cmi.ac.in/~ramprasad/00041817.pdf (hope there are no copyright issues!)
Ramprasad
CC BY-SA 2.5
2010-11-15T11:08:35.523Z
2010-11-15T12:14:19.653Z
2010-11-15T12:14:19.653Z
V Vinay
<p>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.</p>

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

CC BY-SA 2.5
2010-11-15T13:58:56.583Z
2010-11-15T14:07:26.750Z
2010-11-15T14:07:26.750Z
Mohammad Al-Turkistany
<p>$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:</p>

<p>For general graphs, <a href="http://www.cse.iitk.ac.in/users/manindra/other/Poly-Machings.pdf">Agrawal-Hoang-Thierauf</a> showed that given the promise that the number of perfect matchings is small, there is an $NC^2$ algorithm to enumerate all of them. </p>

<p>For the class of planar graphs, the <a href="http://en.wikipedia.org/wiki/Pfaffian">pfaffian</a> 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 "<a href="http://people.seas.harvard.edu/~valiant/holographic11-07.pdf">Holographic algorithms</a>" for various problems) <a href="http://www.imsc.res.in/%7Emeena/papers/pfaffians.ps.gz">Mahajan-Subramanya-Vinay</a> 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$.)</p>

<p>And a recent result of <a href="http://eccc.hpi-web.de/report/2010/151/">Vinodchandran-Tewari</a> 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 <a href="http://drops.dagstuhl.de/opus/volltexte/2008/1346/pdf/22011.DattaSamir.Paper.1346.pdf">Datta-Kulkarni-Roy</a></p>

<p>Hope this helps.</p>

CC BY-SA 2.5
2010-11-15T10:46:00.013Z
Yes, I've noticed of the result by Vinodchandran-Tewari. In fact, this post is motivated by their result in some way, though not directly. I'll check the paper by Agrawal-Hoang-Thierauf!
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-11-15T10:33:21.003Z
2010-11-15T19:52:45.827Z
2010-11-15T19:52:45.827Z
Ramprasad
<p>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. </p>

<p><strong>Perfect Matching</strong> 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 <a href="http://en.wikipedia.org/wiki/Edmonds&#39;s_matching_algorithm" rel="noreferrer">Blossom algorithm</a> by Edmonds, and a <a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KUW86/KUW86.pdf" rel="noreferrer">RANDOMIZED parallel algorithm</a> by Karp, Upfal and Wigderson in 1986, only a few subclasses of graphs are known to have $\mathsf{NC}$ algorithms. </p>

<p>In Jan. 2005 there's a post in the blog <a href="http://blog.computationalcomplexity.org/2005/01/mandatory-technical-post-by-guest.html" rel="noreferrer">Computational Complexity</a> that claims it remains open whether Perfect Matching is in $\mathsf{NC}$. My question is:</p>

<blockquote>
  <p>Is there any progress since then, beyond the randomized $\mathsf{NC}$ algorithm?</p>
</blockquote>

<p>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!</p>

<hr>

<p><strong>EDIT at 12/27:</strong></p>

<p>Thank you for all your help, I try to summarize all the results in one figure:
<img src="https://i.sstatic.net/prFbR.png" alt="Relations between classes related to Matching"></p>

<p>The lowest known classes contain the following problems:</p>

<ul>
<li>Matching in general graphs: $\mathsf{RNC}$ [<a href="http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KUW86/KUW86.pdf" rel="noreferrer">KUW86</a>], $\mathsf{RNC}^2$ [<a href="http://portal.acm.org/citation.cfm?id=167213" rel="noreferrer">CRS93</a>]</li>
<li>Matching in bipartite planar/constant genus graphs: $\mathsf{UL}$/$\mathsf{SPL}$ [<a href="http://www.eccc.uni-trier.de/report/2010/201/download" rel="noreferrer">DKT10</a>]/[<a href="http://arxiv.org/abs/1004.5080" rel="noreferrer">DKTV10</a>]</li>
<li>Matching when the total number is polynomial: $\mathsf{SPL}$ [<a href="http://www.eccc.uni-trier.de/report/2009/091/revision/1/download/" rel="noreferrer">H09</a>]</li>
<li>Lex-first maximal matching: $\mathsf{CC}$ [<a href="ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/89/1278/CS-TR-89-1278.pdf" rel="noreferrer">MS89</a>]</li>
</ul>

<p>Furthermore, under plausible complexity assumption: $\mathsf{SPACE[n]}$ requires exponential circuits, Matching in general graphs is in $\mathsf{SPL}$ [<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.9350&amp;rep=rep1&amp;type=pdf" rel="noreferrer">ARZ98</a>].</p>

CC BY-SA 3.0
2016-02-20T10:29:11.563Z
@Hsien-ChihChang張顯之 Isnt L in NC which is in NC^2 which is in P?
Turbo
CC BY-SA 2.5
2010-11-15T05:35:56.307Z
Perhaps not directly relevant, but there's been some progress in deterministic algorithms to count number of perfect matchings,ie Gamarnik's "Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix"
Yaroslav Bulatov
CC BY-SA 2.5
2010-11-15T08:54:12.763Z
There is a related post here by Robin Kothari: http://cstheory.stackexchange.com/questions/1317/problems-between-nc-and-p-how-many-have-been-resolved-from-this-list
Hsien-Chih Chang 張顯之
<cc.complexity-theory><ds.algorithms><reference-request><graph-algorithms><dc.parallel-comp>
Deterministic Parallel algorithm for perfect matching in general graphs?
Hsien-Chih Chang 張顯之
# Deterministic Parallel algorithm for perfect matching in general graphs?

(Asked by: username_0 on 2010-11-15)

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](http://en.wikipedia.org/wiki/Edmonds's_matching_algorithm) by Edmonds, and a [RANDOMIZED parallel algorithm](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KUW86/KUW86.pdf) 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](http://blog.computationalcomplexity.org/2005/01/mandatory-technical-post-by-guest.html) 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:
![Relations between classes related to Matching](https://i.sstatic.net/prFbR.png)

The lowest known classes contain the following problems:

* Matching in general graphs: $\mathsf{RNC}$ [[KUW86](http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/KUW86/KUW86.pdf)], $\mathsf{RNC}^2$ [[CRS93](http://portal.acm.org/citation.cfm?id=167213)]
* Matching in bipartite planar/constant genus graphs: $\mathsf{UL}$/$\mathsf{SPL}$ [[DKT10](http://www.eccc.uni-trier.de/report/2010/201/download)]/[[DKTV10](http://arxiv.org/abs/1004.5080)]
* Matching when the total number is polynomial: $\mathsf{SPL}$ [[H09](http://www.eccc.uni-trier.de/report/2009/091/revision/1/download/)]
* Lex-first maximal matching: $\mathsf{CC}$ [[MS89](ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/89/1278/CS-TR-89-1278.pdf)]

Furthermore, under plausible complexity assumption: $\mathsf{SPACE[n]}$ requires exponential circuits, Matching in general graphs is in $\mathsf{SPL}$ [[ARZ98](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.9350&rep=rep1&type=pdf)].

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, graph-algorithms, dc.parallel-comp

> **Comments:**
> **username_2**: Perhaps not directly relevant, but there's been some progress in deterministic algorithms to count number of perfect matchings,ie Gamarnik's "Deterministic Approximation Algorithm for Computing a Permanent of a 0,1 matrix"  
> **username_0**: There is a related post here by Robin Kothari: http://cstheory.stackexchange.com/questions/1317/problems-between-nc-and-p-how-many-have-been-resolved-from-this-list  
> **username_1**: @Hsien-ChihChang張顯之 Isnt L in NC which is in NC^2 which is in P?  

---

## 5 answers

### Answer by username_6 on 2010-11-15. Score: 13 | Accepted answer

$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](http://www.cse.iitk.ac.in/users/manindra/other/Poly-Machings.pdf) 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](http://en.wikipedia.org/wiki/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](http://people.seas.harvard.edu/~valiant/holographic11-07.pdf)" for various problems) [Mahajan-Subramanya-Vinay](http://www.imsc.res.in/%7Emeena/papers/pfaffians.ps.gz) 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](http://eccc.hpi-web.de/report/2010/151/) 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](http://drops.dagstuhl.de/opus/volltexte/2008/1346/pdf/22011.DattaSamir.Paper.1346.pdf)

Hope this helps.

> **Comments:**
> **username_0**: Yes, I've noticed of the result by Vinodchandran-Tewari. In fact, this post is motivated by their result in some way, though not directly. I'll check the paper by Agrawal-Hoang-Thierauf!  

---

### Answer by username_3 on 2017-04-11. Score: 10

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 by username_4 on 2010-11-15. Score: 8

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.

> **Comments:**
> **username_0**: Welcome to TCS Stack Exchange!  
> **username_0**: Now I found [the paper](http://www.eccc.uni-trier.de/report/2010/201/download) by Datta, Kulkarni and you. I'll read it asap, Thank you!!  

---

### Answer by username_5 on 2010-11-15. Score: 7

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.](http://ieeexplore.ieee.org/iel2/250/1606/00041817.pdf)

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 username_6. But here is another link to the [paper.](http://bit.ly/d5jJcT)

> **Comments:**
> **username_0**: Oops, I have no account to access the paper. What is the title of it?  
> **username_6**: "The complexity of circuit value and network stability". I've put a copy of the paper here: http://www.cmi.ac.in/~ramprasad/00041817.pdf (hope there are no copyright issues!)  

---

### Answer by username_7 on 2010-11-15. Score: 1

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


---

