How to compute an injective/surjective map with minimum weight?

user_744221 0
Viewed 169

We are given an m x n matrix w which represents the edge weights in a complete bipartite graph K_m,n. We wish to find a map {1,...,m} -> {1,...,n} with minimal weight, which is injective or surjective. Choosing a map is equivalent to, for every vertex v in {1,...,m}, choosing exactly one edge incident to v.

Let m<=n. An injective function with minimal weight can be found by searching for the perfect matching with minimal weight. In Python, this is implemented in scipy:

import numpy as np
import scipy, scipy.optimize
w=np.random.rand(5,10)
print(scipy.optimize.linear_sum_assignment(w))

Let m>=n. How can a surjective function with minimal weight be found? I'm looking for a concrete implementation in Python.

implementation graph-theory algorithm python
1 Answers

EDIT: It turns out I might have misunderstood your question.

From injective to surjective

If m > n, and you already have an algorithm that handles the case m <= n, then swap the two components. Your algorithm will give you an injective function from the second component to the first. Take the inverse of that function; it will be a surjective function from a subset of the first component to the second component.

Using networkx

What you are looking for is a maximum-cardinality matching in a bipartite graph.

The python library networkx contains several functions for that. Standard problems are "maximum-cardinality matching" and "maximum-weight matching"; I'd be surprised if there were a function to solve your "minimum-weight maximum-cardinality matching" problem directly.

However; it looks to me as if your problem was equivalent to finding a maximum-weight matching in the weighted graph obtained by replacing every weight w by W-w, where W is some very large value (for instance, three times the maximum weight in the original graph).

By including this large value W in the weight of every edge, you're forcing the maximum-weight matching to be a maximum-cardinality matching. And by including the negative value -w, you're asking the algorithm to find edges with the smallest possible original weight in the original graph.

user_30807230
Related