# Counting matchings in a bipartite matching-covered graph

A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & Plummer). It is well-known that for bipartite graphs this is equivalent to the existence of ear decompositions.

What I'd like to know is whether the problem of counting the perfect matchings - which is very difficult in general, even for bipartite graphs, being equivalent to the permanent etc. - becomes easier when restricted to bipartite matching-covered graphs.

For example, it seems to me that the number of matchings ought to be somehow readable off the ear-decomposition but I don't quite see how.

-

Yes, it is still just as hard. Given an arbitrary bipartite graph, in polynomial time you can remove every edge that is not in a perfect matching (test one edge at a time), thus reducing the problem to a matching-covered graph.

-
Thanks, that makes a lot of sense. But what aboud the ear-decomposition? Can't we make it to good use somehow? I am willing even to settle for a non-polynomial but sane algorithm that will work in small cases. – Felix Goldberg May 2 '13 at 16:10
Since a perfect matching can lie along an ear in two different ways, it seems that the recursion provided by an ear decomposition would have exponential complexity. But I'd love to be proved wrong.... – Brendan McKay May 2 '13 at 23:11