3
$\begingroup$

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?

2 Answers 2

2

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.

2

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.