Optimum matchings in weighted bipartite graphs

Abstract

Given an integer weighted bipartite graph $\{G=(U\bigsqcup V,E),w:E\to \mathbb{Z}\}$ we consider the problems of finding all the edges that occur in some minimum weight matching of maximum cardinality and enumerating all the minimum weight perfect matchings. Moreover, we construct a subgraph $G_{cs}$ of $G$ which depends on an $\epsilon$-optimal solution of the dual linear program associated to the assignment problem on $\{G,w\}$ that allows us to reduced this problems to their unweighed variants on $G_{cs}$. For instance, when $G$ has a perfect matching and we have an $\epsilon$-optimal solution of the dual linear program associated to the assignment problem on $\{G,w\}$, we solve the problem of finding all the edges that occur in some minimum weight perfect matching in linear time on the number of edges. Therefore, starting from scratch we get an algorithm that solves this problem in time $O(\sqrt{n}m\log (nW))$, where $n=|U|\ge |V|$, $m=|E|$, and $W=\max \{|w(e)|:e\in E\}$.

11 pages