1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Have you searched for "weighted bipartite matching"? $\endgroup$ – Apass.Jack Dec 12 '18 at 6:27
  • $\begingroup$ 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? $\endgroup$ – Shubham Jain Dec 14 '18 at 5:43
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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