The Hungarian algorithm can be seen to take as input a complete weighted bipartite graph and outputs an optimal matching, maximising or minimising the sum of all the edges. Crucially, this algorithm runs in time polynomial in the size of the input graph.
My question is as follows. Suppose that we start from a complete bipartite graph where some pairs of vertices have multiple weighted edges between them, and suppose that the number of edges between any pair of vertices is bounded by some constant. How can one modify the Hungarian algorithm so that it outputs the optimal matching for this class of graphs, so that the running time is still polynomial?
Best Answer
You don't even need the number of parallel edges to be bounded. For each pair of adjacent vertices, only keep the edge with the maximum (minimum) weight. Then run the Hungarian algorithm on the resulting simple graph to obtain a perfect matching with maximum (minimum) weight. Clearly, this does the trick since for any other perfect matching replacing all edges with parallel edges of maximum (minimum) weight gives a perfect matching with greater (lower) weight.