# How to modify the hungarian algorithm for bipartite graphs with multiple edges with some already imposed connections

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?

• I have taken the liberty to slightly modify your title in order to convey the contents of the question. Do you agree ? Commented Dec 30, 2022 at 17:01
• It looks fine, I agree. Just one comment: why did you add the 'already imposed connections'? Not that it's wrong, but thought I'd ask. Commented Dec 31, 2022 at 10:34
• You are right. I propose you to modify yourself this title as you want for example by deleting the last words. Commented Dec 31, 2022 at 12:10