<p>Reduce to a flow problem: Split each left node into <span class="math-container">$L_i$</span> into two nodes <span class="math-container">$L_i$</span> and <span class="math-container">$L'_i$</span> connected with an edge with capacity <span class="math-container">$b(i)$</span> , give the orignal edges between left and right cpacity 1 and connect left side (the new split node) to super source and the right side to a super sync.
And solve max flow (can be done by repeatly finding shortest path and create reverse edges when allocating capacity which allows cancelling matching if it allows us to match more).</p>

CC BY-SA 4.0
2022-08-17T19:06:05.953Z
2022-08-17T19:06:05.953Z
Meir Maor
<p>Consider the following problem, of which I am pretty certain that it is polynomially solvable.</p>
<p>Given some arbitrary bipartite Graph <span class="math-container">$G=(L\cup R,E)$</span> and some vector <span class="math-container">$b\in\mathbb{N}^{|L|}$</span> with <span class="math-container">$\sum_{i=1}^{|L|} b(i)\geq|R|$</span> (so basically each &quot;left&quot; vertex gets some capacity which means it can at most match <span class="math-container">$b(i)$</span> vertices from the other side).</p>
<p>The question is: Is there a Matching such that each <span class="math-container">$v\in L$</span> gets matched at most <span class="math-container">$b(i)$</span> times <strong>and</strong> matches/covers each vertex <span class="math-container">$r\in R$</span> exactly once.</p>
<p>What algorithm could solve this in polynomial runtime? Can you
recommend some useful literature?</p>

CC BY-SA 4.0
2022-08-17T17:50:30.857Z
You may assume $b(i)\le|R|$. Split each left vertex $i$ into $b(i)$ copies, compute a maximum-cardinality matching, and check it has size $|R|$.
Emil Jeřábek
CC BY-SA 4.0
2022-08-17T18:36:30.503Z
Or reduce to max flow with integer capacities.
Neal Young
CC BY-SA 4.0
2022-08-17T23:23:13.817Z
This is not a research level question.
Chandra Chekuri
<graph-theory><graph-algorithms><time-complexity><matching>
Unweighted bipartite $b$-Matching
NoteMyQuestion
# Unweighted bipartite $b$-Matching

(Asked by: username_0 on 2022-08-17)

Consider the following problem, of which I am pretty certain that it is polynomially solvable.

Given some arbitrary bipartite Graph $G=(L\cup R,E)$ and some vector $b\in\mathbb{N}^{|L|}$ with $\sum\_{i=1}^{|L|} b(i)\geq|R|$ (so basically each "left" vertex gets some capacity which means it can at most match $b(i)$ vertices from the other side).

The question is: Is there a Matching such that each $v\in L$ gets matched at most $b(i)$ times **and** matches/covers each vertex $r\in R$ exactly once.

What algorithm could solve this in polynomial runtime? Can you
recommend some useful literature?

**Tags:** graph-theory, graph-algorithms, time-complexity, matching

> **Comments:**
> **username_1**: You may assume $b(i)\le|R|$. Split each left vertex $i$ into $b(i)$ copies, compute a maximum-cardinality matching, and check it has size $|R|$.  
> **username_2**: Or reduce to max flow with integer capacities.  
> **username_3**: This is not a research level question.  

---

## 1 answers

### Answer by username_4 on 2022-08-17. Score: 0

Reduce to a flow problem: Split each left node into $L\_i$ into two nodes $L\_i$ and $L'\_i$ connected with an edge with capacity $b(i)$ , give the orignal edges between left and right cpacity 1 and connect left side (the new split node) to super source and the right side to a super sync.
And solve max flow (can be done by repeatly finding shortest path and create reverse edges when allocating capacity which allows cancelling matching if it allows us to match more).


---

