= Bipartite b-matching
{title2=$F\subseteq E,\quad\deg_F(v)\leq b_v$}
For a <bipartite graph> with <bipartition> $L,R$ and <nonnegative integer> bounds $b_v$, a <bipartite b-matching> is an <edge> <subset> $F$ whose <degree of a vertex> is at most $b_v$ at each $v$. Taking $b_v=1$ gives a <matching in a graph>. To maximize $|F|$, build a <flow network> with arcs $s\to u$ of <flow network edge capacity> $b_u$ for $u\in L$, arcs $u\to v$ of <flow network edge capacity> one for $uv\in E$, and arcs $v\to t$ of <flow network edge capacity> $b_v$ for $v\in R$. The <integral max-flow theorem> gives an integral optimum. Select precisely the middle arcs with <flow> one. <Flow conservation> identifies their endpoint degrees with the outside arc <flows>, and the <flow value> is $|F|$. Conversely, every such <edge> <subset> supplies a <feasible flow> of that value. This proves the reduction and its optimality.
Back to article page
