0
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ May 2, 2013 at 16:10
  • $\begingroup$ 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.... $\endgroup$ May 2, 2013 at 23:11

Your Answer

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

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