4
$\begingroup$

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.

$\endgroup$
2
+100
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are we using the same definition of augmenting path? I'm under the impression your answer is aimed at the "maximum flow" meaning of augmenting path, so a positive flow from $s$ to $t$. However, what I mean is an augmenting path in the context of a matching, so a path where edges are alternatively in and not in matching $M$ (See for example the definition here, under paragraph 6.1) $\endgroup$ – Radical Jul 27 '17 at 8:28
  • $\begingroup$ @Radical aha! Perfect. Yes we were using different definitions, I'll edit to use yours in a few hours. The good news is these can change choices too, I just need a slightly more careful argument on (1). (2) is still correct, because the graph is bipartite you can make the edges directed st bellman must pick an augmenting path by this def. The trick is not bad. The question was phrased for a hint, do you want the full arguments? $\endgroup$ – Artimis Fowl Jul 27 '17 at 15:35
  • $\begingroup$ Thanks! I'm giving you the bounty regardless, but if you have time there's a couple of things I don't totally understand yet. In your second, "No disjoint edges", argument for (1), you claim that creating the augmenting path in the way you describe will result in matching $M'_{k+1}$. While I see this happening if I make an example and it sort of makes sense intuitively, I don't see how augmenting $M_k$ along $M'_{k+1}$'s edges guarantees to get you to $M'_{k+1}$ (although I see how you would always get an augmenting path). $\endgroup$ – Radical Jul 28 '17 at 8:31
  • $\begingroup$ Then for (2), even if we can find an augmenting path in $\mathcal{O}(n^3)$, wont we need to find all augmenting paths in each iteration to find the minimal length one? Let's say we can find one augmenting path in $\mathcal{O}(n^3)$. In the worst case there are $\frac{n}{2}$ augmenting paths getting us to $\mathcal{O}(n^4)$ to find the shortest one, and we need to do so for $\frac{n}{2}$ iterations getting us $\mathcal{O}(n^5)$ $\endgroup$ – Radical Jul 28 '17 at 8:31
  • $\begingroup$ I have updated for your concerns with $(2)$, the trick being that Bellman ford finds this shortest path. It's not immediately clear to me that DFS would do the same, as they suggest in your earlier link. I will update for your concerns on $(1)$ in awhile. $\endgroup$ – Artimis Fowl Jul 28 '17 at 17:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.