Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Consider a bipartite Garph $G=(L \cup R, E)$. Naturally, a b-Matching problem is to find a set of edges $M \subset E$, such that each node in $L$ and $R$ are adjuscent to maximum $b$ neighbors, and a weight function $w(e), e \in E$ is maximized. What if we have different $b$? e.g., $b(v)=5, \forall v \in R$ and $b(v)=2, \forall v \in L$. How do you call the problem? Is is constrained matching, or k-cardinality assignment, or what? I need to find some literature for it.
Thanks!
I'm not sure if it's a standard problem, but it seems this problem is described in Solving the Many to Many assignment problem by improving the Kuhn–Munkres algorithm with backtracking.
(the other closest things I found are https://en.wikipedia.org/wiki/Generalized_assignment_problem and https://link.springer.com/content/pdf/10.1007/BF02190106.pdf, but they are talking about one-to-many assignments).
Anyway, you can solve it using maximum flow. For $b=1$ (usual matching) you can check these slides, namely this picture:
I.e. we create auxiliary vertices $s$ and $t$, create edges $(s, u)$ for all $u$ in the left part and $(v, t)$ for all $v$ in the right part. All edges have capacity one. By solving maximum flow on this graph, you'll find maximum matching (Note: you have to find an integral solution, i.e. where flow through each edge is either 1 or 0, but standard maximum flow algorithms will do that).
For $b>1$ the graph is the same. The difference is that all edges $(s,u)$ have capacity $b_L$ and $(v,t)$ have capacity $b_R$.
If your edges have weights, then you can negate edge weights and solve min-cost max-flow on this graph.
