-1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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|$. $\endgroup$
    – Emil Jeřábek
    Aug 17, 2022 at 17:50
  • 1
    $\begingroup$ Or reduce to max flow with integer capacities. $\endgroup$
    – Neal Young
    Aug 17, 2022 at 18:36
  • 1
    $\begingroup$ This is not a research level question. $\endgroup$
    – Chandra Chekuri
    Aug 17, 2022 at 23:23

1 Answer 1

Reset to default
0
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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