Topic summary
Maximum-weight matching
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 blossom algorithm, or Gabow's 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.