Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.