2
$\begingroup$

Consider a maximum weight matching problem on a bipartite graph $G = (E,V)$ with $V = U \cup W$ such that the sets of vertices $U$ and $W$ have different cardinalities, i.e., $|U| \neq |W|$. Given this discrepancy in the number of vertices in $U$ and $W$, will the LP relaxation of this problem still have integral solutions?

$\endgroup$
1
$\begingroup$

Yes! The result is due to the vertex-edge incidence matrix of any bipartite graph being totally unimodular. The proof of that result doesn't depend on the sizes of $U,W$ (as long as none are nonempty, then the graph is not bipartite at all).

$\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.