[Math] Algorithm for maximum weight matching

bipartite-graphsgraph theorymatching-theory

I have been given the following algorithm for finding a maximum weight matching in a bipartite graph:

  1. $M=\emptyset$

  2. Find augmenting path $C$ with minimal length when looking at length function $l_{ij} = w_{ij}$ if $(v_2, v_j)\in M$, or $l_{ij} = -w_{ij}$ otherwise. Stop when there is no augmenting path, or every augmenting path has non-negative length.

  3. $M = M \oplus C$ and go back to step 2

Now I am being asked:

  1. Prove correctness by showing that in iteration $k$, matching $M$ has maximal weight compared to any other matching of cardinality $k$.

  2. Show that the complexity is $\mathcal{O}(n^4)$.

For (1), I was thinking of doing it by induction, but this doesn't seem to work: The case for the first iteration is clear, and that the weight of the matching grows every iteration is obvious as well, but how do we know there isn't some way to first choose "lesser" matchings and then finally find an augmenting path which gives the best possible matching $M$ (I don't know if induction is the best way by the way, but I wouldn't know how else to approach it).

For (2), I would think the complexity lies in finding the augmenting path in step 2 of the algorithm. However, I don't see how the $n^4$ would come into play here.

If anyone has any hints or ways in which I could try to approach this, I would be most grateful.

Best Answer

First, $M= M \oplus C$ means that we add all edges in $C$ to $M$, and if any edge is in $C$ and old $M$, we remove it from $M$.

For $(1)$, induction is a fine approach. The key observation is that an augmenting path $C$ can 'undo' all previous edge choices, provided we keep the same matched nodes. Fortunately this is always the case.

Suppose for some maximum weight matching with $k$ edges $M_k$ with total weight $w_k$ there is a maximum weight matching with $k+1$ edges with some edge that is disjoint from the matched vertexes of $M_k$. Then there exists $k+1$ edges $e_i$ such that:

  1. $e_{k+1} = (u,v) \not \in M_k$ and further $u,v$ are unmatched by $M_k$ (by assumption)
  2. $w_k \geq (\sum_i w(e_i) ) - e_{k+1} \implies w_k + w(e_{k+1}) \geq \sum_i w(e_i)$ (first part follows from $M_k$ being maximal with $k$ edges)

Note that $C = \{e_{k+1} \}$ would be a valid augmenting path, giving a matching with $k+1$ edges. This is because $e_{k+1}$ is disjoint from $M_k$.

Meanwhile, suppose there is a maximum weight matching $M'_{k+1}$ with $k+1$ edges that has no disjoint edges from $M_k$. Then we can follow a path from the first new vertex, alternating between edges in $M_k$ and the edges in $ M'_{k+1}$ (and skipping edges both share). Because they are both matchings, and they share matched vertecies, every matched vertex in $M_k$ has an edge from $M'_k$ and from $M_k$. If this happens to be the same edge, the agumenting path need not go through this node. If they are different, then that node can be part of an augmenting path coming in/out from one and out the other (hence alternating being in $M$ and out of $M$). Further, if they are not the same then the vertexes they connect to must also be matched differently by $M_k$ and $M'_k$ (otherwise some node would be matched twice). Therefore these nodes with different matchings in $M$ and $M'$ form a path, and since $M'_k$ is maximal, this path will be a minimal augmenting path.

Thus in either case, be there a maximum matching on $k+1$ edges that is disjoint or overlapping, we can find an augmenting path that will make $M$ do just as good.

For $(2)$, one way to find an augmenting path is via Bellman Ford, which takes $O(|V||E|) = O(n^3)$ time (Assuming one has the maximum of $O(n^2)$ edges). Naively you would have to run bellman from every start node, but you can modify the graph so that Bellman ford finds the shortest augmenting path with only one call. The trick is to modify the graph slightly before giving it to the algorithm. We add 2 new vertexes $s,t$, with $s$ connected to one bipartition by edges with weight $0$, and $t$ connected to the other. You then just need to find the minimal path from $s$ to $t$, which bellman ford does.

This only adds a linear number of edges and a constant number of vertecies, so the asymptotic runtime is not changed. Check how many calls we need to Bellman Ford (or your favorite $O(n^3)$ shortest paths algorithm), and we're done.

Related Question