Maximum-weight matching is an optimization problem in graph theory in which the goal is to find a matching of maximum possible total weight in an edge-weighted graph. A matching is an independent edge set (that is, a set of edges in which none of the members share a common endpoint). The weight of a matching is the sum of the weights on its edges. The problem is a generalization of the maximum cardinality matching problem because it allows edges to carry arbitrary numerical weights. When all edge weights are equal, a maximum-weight matching is equivalent to a maximum cardinality matching. The maximum-weight matching problem is solvable in polynomial time using, for example, the O ( E V 2 ) {\displaystyle O(EV^{2})} blossom algorithm, or Gabow's O ( V 3 ) {\displaystyle O(V^{3})} algorithm. This contrasts with the problem of computing the (weighted) maximum independent set of vertices in a graph, which is NP-hard. By adjusting the given edge weights, algorithms for the maximum-weight matching problem can also be used to solve the maximum cardinality maximum-weight matching problem, where the objective is to find, among all matchings with maximum cardinality, one whose total weight is maximised. Similar ideas can also be used to solve the maximum cardinality minimum weight matching problem. In cases where the edge-weighted graph is bipartite, such problems are also known as the assignment problem.
Definition Given an undirected graph G = ( V , E , w ) {\displaystyle G=(V,E,w)} with vertex set V {\displaystyle V} , edge set E {\displaystyle E} , and weight function w : E → R {\displaystyle w:E\to \mathbb {R} } , a maximum-weight matching is an independent set of edges M ⊆ E {\displaystyle M\subseteq E} that maximises the total weight
w ( M ) = ∑ e ∈ M w ( e ) . {\displaystyle w(M)=\sum _{e\in M}w(e).}
The edge weights may be positive, negative, or mixed.
Maximum cardinality weighted matchings
A commonly occurring variant of the problem involves computing a matching that contains as many edges as possible. The total weight of the matching is then used as a secondary measure. To solve the maximum-cardinality maximum-weight matching problem on G = ( V , E , w ) {\displaystyle G=(V,E,w)} , a new graph G ′ = ( V , E , w ′ ) {\displaystyle G'=(V,E,w')} is formed in which, for each edge e ∈ E {\displaystyle e\in E} ,
w ′ ( e ) = C + w ( e ) , {\displaystyle w'(e)=C+w(e),}
where C {\displaystyle C} is an appropriate positive constant. A maximum-weight matching in G ′ {\displaystyle G'} then corresponds to a maximum cardinality maximum-weight matching in G {\displaystyle G} . To solve the maximum cardinality minimum weight matching problem, set
w ′ ( e ) = C − w ( e ) . {\displaystyle w'(e)=C-w(e).}
Again, a maximum-weight matching on G ′ {\displaystyle G'} yields a maximum cardinality minimum weight matching in G {\displaystyle G} . In both cases, a constant C {\displaystyle C} is needed to force the algorithm to favor matchings with greater cardinality regardless of the edge weights in G {\displaystyle G} . Any value of
C > 2 ∑ e ∈ E | w ( e ) | {\displaystyle C>2\sum _{e\in E}|w(e)|}
is sufficient for this purpose.
Algorithms and implementations The maximum-weight matching problem is solvable in polynomial time. Well-known algorithms include:
… excerpt ends here. Continue reading the full article.
