Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-129 | 6th October 2006 00:00

The polynomially bounded perfect matching problem is in NC^2


Authors: Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf
Publication: 11th October 2006 00:01
Downloads: 1315


The perfect matching problem is known to
be in P, in randomized NC, and it is hard for NL.
Whether the perfect matching problem is in NC is one of
the most prominent open questions in complexity
theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem
for bipartite graphs with polynomially bounded permanent.
They showed that for such bipartite graphs
the problem of deciding the existence of a perfect matchings is in NC^2,
and counting and enumerating all perfect matchings is in NC^3.

In this paper
we extend and improve these results.
We show that for any graph that has a
polynomially bounded number of perfect matchings,
we can construct all perfect matchings in NC^2.
We extend the result to weighted graphs.

ISSN 1433-8092 | Imprint