In the “marriage problem” we have N boys and N girls, as well as the NxN binary matrix telling us which pairs are suitable, and I want each girl to become attached to the boy. (i.e. we want to find the perfect match in a bipartite graph).
Hall's theorem says that you can find a perfect match if each collection of boy nodes is collectively adjacent to at least a lot of girl nodes; and there are fast extended path algorithms that find perfect matches.
I am looking for an effective way to search for collections of boy nodes that all together are displaced in exactly the same way as many girl nodes (i.e., we have equality in the Hall criterion). These boys should be paired with these girls, and the rest of the boys with the rest of the girls, so that all perfect matches respect this separation.
My graph theory is a little rusty, of course, there should be a better way than listing all 2 ^ N subsets and counting each of the neighbors?
source
share