Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. 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

Given two sets A and B of sizes |A| = n and |B| = m, where m >= n. There are edges from set A to set B. I need to find the number of matchings where all of vertices in set A have been matched with one vertex in set B. Is it possible to caclulate this quantity ?

(I have very little knowledge of Graph Thory and Bipartite Matching or how it is computed)

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

A matching in which all the vertices in $A$ are matched is known as a perfect matching. When $n = m$, you need to compute the permanent of the bipartite adjacency matrix (defined in the same way as the determinant, only without the signs). This is conjectured to be rather difficult unfortunately, even in this special case in which the matrix in question is zero-one. The permanent-vs.-determinant question is analogous to the more famous P-vs.-NP question.

When $m > n$, you can add $m-n$ dummy vertices to $A$ and connect them to all vertices in $B$. The number of perfect matchings in the new graph is exactly $(m-n)!$ times the number of perfect matchings in the old graph.

share|cite|improve this answer
Thanks Yuval. Went through the link. It seems the computation for a permanent has a complexity of O(n*2^n). Far beyond the Complexiy I require. I guess I will just have to think of a different approach to my problem :) – Kyuubi Dec 25 '13 at 14:37

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.