Maximum bipartite matching in disconnected graph

Question

How do you find the maximum bipartite matching when your graph has several components ? Each component can be colored in two ways. How do you decide the two sets X and Y in order to run the maximum matching routine ?

Answer 1

Don't look at a matching from the point of view of the edges, look at is as a set of edges. This point of view makes it clearer that no matter how you join the subresults it will still be OK latter on.

1. Separate your graph into connected components

2. Find a maximum matching for each graph component, using your algorithm of choice.

3. The union of the matchings found is a maximum matching of the whole graph.

Answer 2

If your graph has several different connected components, you can find the maximum matching in the graph by just finding the maximum matching in each of those components and returning their union.

As for how to decide the sets X and Y, many algorithms exist for detecting whether a particular graph is bipartite and, if so, assigning labels to the nodes to recover those two groups. You can do this with a modified DFS or BFS fairly easily. Consequently, an algorithm for your problem might be

1. Run a DFS over the entire graph to break it into connected components.
2. For each of those components:
   1. Run a DFS on those components to recover which nodes are in the groups X and Y.
   2. Use a maximum bipartite matching algorithm to find a maximum matching in that component.
3. Combine all the results together to get the overall answer.

Hope this helps!

Answer 3

I don't know about disconnected graph but if you have a complete graph like I have this might be interesting for you: http://wilanw.blogspot.com/2009/09/maximumminimum-weighted-bipartite.html. It's using a modified Floyd-Warshall algorithm to find the maximum matching. I don't know about the difference between this and the Hungarian algorithm.