4
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • 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$ – Jukka Suomela Oct 7 '12 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$ – Jukka Suomela Oct 7 '12 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$ – Patrick Schmidt Oct 7 '12 at 21:38
  • $\begingroup$ convert this to an answer ? $\endgroup$ – Suresh Venkat Oct 7 '12 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$ – Yoshio Okamoto Oct 10 '12 at 8:07
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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