I have a weighted bipartite graph consisting of two sets $S$ and $P$. ($|S| > |P|$). I need to find a matching so that every node $s$ in $S$ matches a node of $P$. But a node $p$ in $P$ can match multiple nodes of $S$. Each $p$ has an individual limit of how many nodes it can match. The total weight of the matching should be as small as possible.

My research ended quite quick because I do not know the right key words to search for. Does this kind of matching problem have a specific name?

Second question: Do you already know some algorithms I should have a glance at?

  • 3
    $\begingroup$ Terminology: In the most general form, we can have a function $f\colon V \to \mathbb{N}$ that specifies the "limit" for each node, and a subset of edges that satisfies all these constraints is called an $f$-matching. $\endgroup$ Oct 7, 2012 at 20:57
  • 3
    $\begingroup$ Algorithms: In your case a simple approach is to replace each node of $P$ with multiple nodes, and then use a standard algorithm for weighted bipartite matching. $\endgroup$ Oct 7, 2012 at 20:59
  • 2
    $\begingroup$ Thank you. Now I found the Hungarian Algorithm. I will use a new set P* with f(p) nodes for each p in P, than add dummy nodes to S until |S|=|P*|. Than give the Hungarian algorithm a try. $\endgroup$ Oct 7, 2012 at 21:38
  • $\begingroup$ convert this to an answer ? $\endgroup$ Oct 7, 2012 at 21:56
  • 3
    $\begingroup$ It depends on what you want, but the reduction by Jukka is pseudo-polynomial. If you need a polynomial-time algorithm, you can directly use network flow without resorting to duplication of nodes. $\endgroup$ Oct 10, 2012 at 8:07

1 Answer 1


According to the comments above, the problem can be reduced to a weighted bipartite matching / assignment problem.

If $f(p)$ specifies the limit of matches for a node in $P$, we replace each $p$ by $f(p)$ nodes. To assure $|S| = |P|$ we can add dummy nodes to $S$.

Now we can solve the problem by a standard algorithm. E.g. Hungarian Method.


Your Answer

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

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