Matchings in colored bipartite networks

AbstractIn K(n,n) with edges colored either red or blue, we show that the problem of finding a solution matching, a perfect matching consisting of exactly r red edges, and (n−r) blue edges for specified 0⩽r⩽n, is a nontrivial integer program. We present an alternative, logically simpler proof of a theorem in (Kibernetika 1 (1987) 7–11) which establishes necessary and sufficient conditions for the existance of a solution matching, and a new O(n2.5) algorithm. This shows that the problem of finding an assignment of specified cost r in an assignment problem on the complete bipartite graph with a 0−1 cost matrix is efficiently solvable