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 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .