1
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ I have taken the liberty to slightly modify your title in order to convey the contents of the question. Do you agree ? $\endgroup$
    – Jean Marie
    Commented Dec 30, 2022 at 17:01
  • $\begingroup$ 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. $\endgroup$
    – Emil Sinclair
    Commented Dec 31, 2022 at 10:34
  • $\begingroup$ You are right. I propose you to modify yourself this title as you want for example by deleting the last words. $\endgroup$
    – Jean Marie
    Commented Dec 31, 2022 at 12:10

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .