Partitioning perfect matchings in a bipartite graph

Question

In the 'marriage problem', we have N boys and N girls and an NxN binary matrix telling us which pairings are suitable, and want to pair each girl to a boy. (i.e. we want to find a perfect matching in a bipartite graph).

Hall's theorem says that you can find a perfect matching if every collection of boy-nodes is collectively adjacent to at least as many girl-nodes; and there are fast augmenting-path algorithms that find perfect these matchings.

I'm looking for an efficient way to find collections of boy-nodes that are collectively adjacent to exactly as many girl-nodes (i.e. we have equality in Hall's criterion). These boys must be paired with these girls, and the rest of the boys with the rest of the girls, so that all perfect matchings respect this partitioning.

My graph theory is a bit rusty, surely there must be a better way than enumerating all 2^N subsets and counting each one's neighbours?

Answer 1

If I'm understanding what you want, then alas, there is no smart way of doing this in polynomial time. Finding such partitions on a general graph is an NP-complete problem.

Answer 2

This is possible in polynomial time. Model your bipartite matching problem as a maximum flow problem in a directed graph. Then use an algorithm for enumerating minimum cuts. Search on Google for "enumerate minimum cuts", or papers by Vazirani & Yannakakis or Yeh & Wang.