Existence of bipartite perfect matching

Question

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.

Answer 1

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.