I need an algorithm for finding in a bipartite graph a matching saturating all vertices of maximum degree. How do I come up with such an algorithm?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The non-trivial part of this question is to prove the existence of such a matching. Let $G$ be a bipartite graph $G$ with max-degree $\Delta$, and let $S$ be the set of vertices of degree $\Delta$. Create a bipartite $\Delta$-regular graph $G'$ from $G$ by adding "dummy" edges (and also dummy vertices, if necessary, to make the graph balanced). The key claim is that all edges in $G'$ that are incident on $S$ are non-dummy edges, and it isn't hard to see why (Exercise!).
By Hall's theorem for regular bipartite graphs, $H$ has a perfect matching, say $M'$. Now, simply delete the dummy edges from $M'$ to get the matching $M$. From the key claim above, it follows that $M$ is indeed a matching in $G$ and it saturates all of $S$.
As for the algorithm, the only non-trivial step in the above proof is to find a perfect matching in a regular graph. This is a standard optimization problem, with a number of beautiful algorithms; see the wikipedia page for details.
As far as I understand, what you have described is the problem of finding perfect b-matching. You may want to google that. There is no existing wikipedia page for this problem, bu some research literature. Check out this personal homepage: www.cs.umd.edu/~bert. This guy was doing this a bit.