Suppose I have a graph with a set of edge, and a weight assigned to each edge. How can I find a maximum-weight matching of the edges? I think this is a classic CO problem but I don't know the name of the algorithm. I need this algorithm to solve an online programming puzzle.
[Math] How to find the maximum-weight matching
graph theory
Related Solutions
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:
- $e_{k+1} = (u,v) \not \in M_k$ and further $u,v$ are unmatched by $M_k$ (by assumption)
- $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.
Consider this example.
The greedy algorithm will pick edges $S=\{(0,2)$ and $(1,3)\}$ for total weight of $2$. The optimal solution is $S^* = \{(0,1), (2,3)\}$ for total weight of $17$.
In the analysis given, for each edge $e$ in $S^*$, you will pick an edge $e'$. Following the description, for $e=(0,1)$ we will pick $e'=(0,2)$, and for $e=(2,3)$ we will pick $(0,2)$ also. So $W' = \{ (0,2), (0,2) \}$. That is why $W'$ can have duplicates.
Hopefully this also shows why elements in $W'$ are only duplicated at most $2$ times. For example: suppose $W'$ contains some edge $(u, v)$. The first time it appears might be because $S^*$ contains $(u, v_1)$ for some other vertex $v_1$. The second time can be $(v, v_2)$ for some $v_2$. To appear a third time, you need either $(v, ?)$ or $(u, ?)$ in $S^*$, but either of these will contradict $S^*$ being a matching.
Lastly, your caveat about 1) is not necessary. Because if $e \in S^*$ and $e \in S$, then we can just choose $e' = e$, and the remainder of the statement still holds.
Best Answer
Many books on operations research have material about matchings and weighted matchings, often only for the bipartite graph case. However, a book that treats both the general and bipartite case is Dieter Jungnickel, Graphs, Networks and Algorithms, Springer, 1999, Chapters 12 and 13.