Maximum weight bipartite matching

2
votes

I have a graph in form of a rectangular grid, i.e. N nodes and 2N edges, all adjacent nodes are connected. This means it is two-colourable, and hence it is possible to do bipartite matching on it.

Each (undirected) edge has a weight assigned to it - either -2, -1, 0, 1 or 2. No other values are allowed

How would I go about finding the matching on this graph that maximises the sum of the weighs in the matching? Pseudocode would be nice, don't bother with specific languages.

Ideally, I am looking for an algorithm that runs in quadratic time - maybe O(n^2 log n) at worst.

Before you propose a solution, I have tried doing a max match using edges of weight 2, then of weight 1 (without going over edges of weight 2). I have scored 98% with this implementation (the problem is from an informatics olympiad), and wondering what is the 100% solution.

1
algorithmgraphmatchingbipartite
Don't you mean 2N edges? And you want the matching to include all nodes, correct? – Beta
Yes, 2N edges (edited to reflect that). And I want the matching to include any number of nodes, as long as the sum of the edges in the matching is maximised. – evgeny
I think you are looking for graph cuts - en.wikipedia.org/wiki/Cut_(graph_theory). The minimum cut algorithm runs O(n^3) though and I doubt anyone here will beat that. – Karel Petranek
@dark_charlie: Why do you say that it will be O(n^3)? Currently, I am thinking of Ford-Fulkerson, which is O(VE), or in my case O(n^2). The only problem is that it is icky to implement. – evgeny
@Evgeny: Ford-Fulkerson is O(V * E^2) where E^2 = 4 * V^2 in your case and that yields O(V^3). – Karel Petranek

1 Answers

3
votes

Not sure why you are thinking of min cut. A cut is not guaranteed to give you matching in this case. What you need to do is solve assignment problem.Assignment Problem. The successive shortest math algorithm solves it in O(EV log V) which in your case is O(n^2 log n).