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.



1 Answer 1


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: enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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