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

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

<p>Now we can solve the problem by a standard algorithm. E.g. Hungarian Method.</p>

CC BY-SA 3.0
2012-10-21T08:02:59.553Z
2012-10-21T08:09:25.363Z
2012-10-21T08:09:25.363Z
Patrick Schmidt
<p>I have a weighted bipartite graph consisting of two sets $S$ and $P$. ($|S| &gt; |P|$).
I need to find a matching so that <strong>every</strong> node $s$ in $S$ matches a node of $P$. But a node $p$ in $P$ can match <strong>multiple</strong> 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.</p>

<p>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?</p>

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

CC BY-SA 3.0
2012-10-07T20:57:23.073Z
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.
Jukka Suomela
CC BY-SA 3.0
2012-10-07T20:59:23.727Z
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.
Jukka Suomela
CC BY-SA 3.0
2012-10-07T21:38:23.170Z
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.
Patrick Schmidt
CC BY-SA 3.0
2012-10-07T21:56:44.303Z
convert this to an answer ?
Suresh Venkat
CC BY-SA 3.0
2012-10-08T06:47:01.373Z
Jukka Suomela, if you put you second comment into an answer I can accept it.
Patrick Schmidt
CC BY-SA 3.0
2012-10-10T08:07:10.530Z
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.
Yoshio Okamoto
<ds.algorithms><graph-theory><graph-algorithms><matching>
Matching on bipartite graph - multiple edges
Patrick Schmidt
# Matching on bipartite graph - multiple edges

(Asked by: username_0 on 2012-10-07)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, matching
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: convert this to an answer ?  
> **username_0**: Jukka Suomela, if you put you second comment into an answer I can accept it.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_0 on 2012-10-21. Score: 3 | Accepted answer

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.


---

