MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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