# Multiple rounds of bipartite matching problem

I have a set of investors (say n), and a set of startups (say m). At the start, I have all the investors say either yes or no to the startup (which corresponds to whether they want to interact with them or not).

Now, I have to conduct a networking event of r rounds considering this scenario. In each round, I match investors with startups they want to meet (one investor with one startup). I want to conduct the rounds such that the sum of the startups they met, across all investors, is maximum.

Now, if r=1, this reduces to the maximum bipartite matching problem. Does anyone have any ideas on how to solve this for r>1? I have been thinking along the lines of having the source and sink edge capacities to be r instead of 1, but I am unable to prove that this works.

• Have you searched for "weighted bipartite matching"? – John L. Dec 12 '18 at 6:27
• Forgive me, but it's not obvious to me how this reduces to the weighted bipartite matching problem. I need a union of r matchings finally, so how would you visualize that being guaranteed? – Shubham Jain Dec 14 '18 at 5:43

You can solve this by a mild extension of the standard reduction to network flow: increase the weight of the edges touching the source and the sink to $$r$$. Any integer flow corresponds to a union of $$r$$ matchings:

• An integer flow corresponds to a bipartite graph of maximum degree $$r$$.
• We can complete this bipartite graph to an $$r$$-regular bipartite graph by adding vertices and edges:
1. Add vertices so that both sides have the same number of vertices.
2. If the graph is not $$r$$-regular, then there must be two vertices $$x,y$$ (one on each side) with degree less than $$r$$. Add $$r$$ new vertices $$x_1,\ldots,x_r$$ and $$y_1,\ldots,y_r$$ to each side (respectively), and connect all of them except $$x_1$$ and $$y_1$$. Connect $$x$$ to $$y_1$$ and $$y$$ to $$x_1$$. This reduces the overall deficiency of the graph $$\sum_v (r - \deg(v))$$ by 1.
• Repeated applications of Hall's theorem shows that the new graph can be decomposed into $$r$$ perfect matchings.
• Restricting these matchings to the original vertices and edges, we obtain a union of $$r$$ matchings.

Schrijver mentions this problem in his Combinatorial Optimization (Vol 1):

Corollary 21.4b. Let $$G = (V,E)$$ be a bipartite graph and let $$k \in \mathbb{Z}_+$$. Then the maximum size of the union of $$k$$ matchings is equal to the minimum value of $$k|V \setminus X| + |E(X)|$$ taken over $$X \subseteq V$$.

This follows by an application of the min cut max flow theorem.