20
$\begingroup$

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: Relations between classes related to Matching

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].

$\endgroup$
  • 1
    $\begingroup$ 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" $\endgroup$ – Yaroslav Bulatov Nov 15 '10 at 5:35
  • 2
    $\begingroup$ There is a related post here by Robin Kothari: cstheory.stackexchange.com/questions/1317/… $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 15 '10 at 8:54
  • $\begingroup$ @Hsien-ChihChang張顯之 Isnt L in NC which is in NC^2 which is in P? $\endgroup$ – T.... Feb 20 '16 at 10:29
13
$\begingroup$

$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.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 15 '10 at 10:46
10
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Oops, I have no account to access the paper. What is the title of it? $\endgroup$ – Hsien-Chih Chang 張顯之 Nov 15 '10 at 11:25
  • 1
    $\begingroup$ "The complexity of circuit value and network stability". I've put a copy of the paper here: cmi.ac.in/~ramprasad/00041817.pdf (hope there are no copyright issues!) $\endgroup$ – Ramprasad Nov 15 '10 at 12:02
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.