3
$\begingroup$

Let $B = G(L, R, E)$ be a bipartite graph. I want to find out whether this graph has a perfect matching. One way to test whether this graph has a perfect matching is Hall's Marriage Theorem, but it is inefficient (i.e $|\mathcal P(L)| = 2^{|L|}$ tests -- not polynomial). I can always find out whether a perfect matching exists by computing a maximum cardinality matching and testing its perfectness, but this involves computing that perfect matching.

Is there an efficient way of deciding whether a perfect bipartite matching exists without computing the matching it self? Ideally I would want an algorithm which is faster than algorithms like Hopcroft Karp or matrix based matching algorithms, which explicitly find out the matching (i.e so not computing the matching makes sense).

Edit: The italic part.

Improve this question
$\endgroup$
4
  • $\begingroup$ You can use Hall's theorem, or use max flow algorithm to detect it. $\endgroup$
    – Bartosz Przybylski
    Mar 29, 2013 at 12:18
  • $\begingroup$ Max flow algorithm computes the matching so it is not an answer to the question I am asking , and Hall's theorem is out of question for reasons stated above (if you can get away without making exponential tests, I would be glad to know how). $\endgroup$
    – Me.
    Mar 29, 2013 at 12:20
  • $\begingroup$ There is also a theorem which stands that grep has perfect matching if $|G| = 2 v(G)$, where $v$ is Matching number but it also requires some computation. $\endgroup$
    – Bartosz Przybylski
    Mar 29, 2013 at 12:27
  • 1
    $\begingroup$ Isn't that just the definition of perfect matching? Besides that is hardly any efficient: en.wikipedia.org/wiki/… $\endgroup$
    – Me.
    Mar 29, 2013 at 12:49

1 Answer 1

Reset to default
5
$\begingroup$

A quick literature review suggests that the fastest algorithm for deciding whether a dense bipartite graph has a perfect matching is still the matrix algorithm, which runs in time $O(|V|^\omega)$. You can reduce the space of the algorithm, see Isolation, Matching and Counting by Allender, Reinhardt and Zhou. A recent paper from 2010, which focuses on planar graphs, suggests that the result of Allender et al. is the best that is known.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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