# Matching on bipartite graph - multiple edges

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?

• 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. Oct 7, 2012 at 20:57
• 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. Oct 7, 2012 at 20:59
• 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. Oct 7, 2012 at 21:38
• convert this to an answer ? Oct 7, 2012 at 21:56
• 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. Oct 10, 2012 at 8:07

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$.