Have any generalizations of maximum weight matching been studied?

Question

For example, one way to view maximum weight matching is that each vertex $v$ gets a utility $f_v= w(e_v)$ that equals the weight of the edge it's matched on, and zero otherwise.

accordingly, a maximum weight matching could then be viewed as maximizing the objective $\sum_v f_v$.

Have any generalizations of maximum weight matching been studied that consider more general objective functions using weighted, multivariate or nonlinear $f_v$ ?

Have other variants been studied that are generalizations in a different way?

pleas provide references if applicable!

Answer 1

Maximum weight matching on $G$ is equivalent to maximum weight independent set on line-graph of $G$, and can be written as follows

$$\max_{\mathbf{x}} \prod_{ij \in E} f_{ij}(x_i,x_j)$$

Here $\mathbf{x}\in\{0,1\}^n$ is a vector of vertex occupations, $f_{ij}(x,y)$ returns 0 if x=y=1, 1 if x=y=0, otherwise weight of the node that's not 0. You can generalize by allowing other choices of $\mathbb{x}$ and $f$, for instance

• Largest proper coloring $\mathbf{x}\in \{1,\ldots,q\}^n, f(x,y)=\delta(x-y)$
• Ising model ground-state $\mathbf{x}\in \{1,-1\}^n, f(x,y)=\exp(J x y)$

If you allow arbitrary non-negative $f$, this becomes the problem of finding the most likely setting of variables in a Gibbs random field with $f$ representing edge interaction potentials. Generalizing further to hypergraphs, your objective becomes

$$\max_{\mathbf{x}} \prod_{e \in E} f_{e}(x_e)$$

Here $E$ is a set of hyper-edges (tuples of nodes), and $x_e$ is restriction of $x$ to nodes in hyperedge $e$.

Example:

• Error correcting decoding, $\mathbf{x} \in \{1,\ldots,q\}^n, f(x_e)=\exp{\text{parity} (x_e)}$
• MAP inference in hypergraph structured probability model, $f$ arbitrary non-negative function

Generalizing in another direction, suppose instead of a single maximum matching, you want to find $m$ highest weighted maximum matchings. This is a special instance of finding $k$ most probable explanations in a probabilistic model. The objective can be now written as

$$sort_\mathbf{x} \prod_{e \in E} f_{e}(x_i,x_j)$$

See [Flerova,2010] for meaning of objective above.

More generally, instead of sort,$\prod$ or $\max,\prod$ over reals, we can consider a general $(\cdot,+)$ commutative semiring where $\cdot$ and $+$ are abstract operations obeying associative and distributive law. The objective we get is now

$$\bigoplus_x \bigotimes_e f_e(x)$$

Here, $\bigotimes$ is taken over all edges of some hypergraph $G$ over $n$ nodes, $\bigoplus$ is taken over $n$-tuples of values, each $f_e$ takes $x$'s to $E$ and $(\bigotimes,\bigoplus,E)$ form a commutative semi-ring

Examples:

• Partition function of spin-interaction models: use $(*,+)$ instead of $(\max,+)$
• Fast Fourier Transform over Abelian groups: use abelian groups instead of $\mathbb{R}$

What's bringing all of these generalizations together is that the best known algorithm for specific instances of the problem above is often the same as the most general algorithm, sometimes called "Generalized distributive law" [Aji, 2000], which works in $O(1)$ time for bounded tree-width hypergraphs.

This puts exact solution of the problems above in a unified framework, however such framework for approximate solution is lacking (and I want to hear about it if you think otherwise)

Answer 2

There are several extensions of the problem to more general structures. For instance:

• Matroid matching (lecture notes, Matroid matching and some applications, Matroid Matching: the Power of Local Search)

• Path-matching (Path-matching problems, Matching, matroids, and extensions)

• Hypergraph matching (Can't find any good references)

Generally, these extensions are NP-hard.

Answer 3

One interesting extension (although maybe it's well known to you) is the variant that allows for partial matching of vertices to other vertices (in the bipartite setting). This variant can also be solved using the Hungarian algorithm, and is known as the transportation problem (the resulting metric is called the transportation metric, the earth-mover distance, the Monge-Kantorovich-Wasserstein distance, or the Mallows distance, depending on who you ask).

Answer 4

Yet another classical problem that can be interpreted as a matching problem with a strange objective function $f_v$ is minimum maximal matching.

Here you can define $f_v$ as follows: $0$ if $v$ is unmatched and adjacent to another unmatched node; $n$ if $v$ is matched; and $n+1$ if $v$ is unmatched but not adjacent to any unmatched node.

Now the value of the objective function $\sum_v f_v$ is $n^2 + n - 2|M| \ge n^2$ if the matching $M$ is maximal; otherwise it is smaller than $n^2$. Hence maximising $\sum_v f_v$ over all $M$ results in the smallest maximal matching $M$.

Finding a smallest maximal matching is an NP-hard optimisation problem, so we can fairly safely say that it isn't just the usual maximum weight matching problem in disguise. Again, note that $f_v$ is "non-local" in the sense that it is not a function of $M$ restricted to the edges incident to $v$.

Answer 5

If you want something that cannot be easily reduced to the maximum-weight matching problem, here is one example: the stable marriage problem.

One interpretation is that in the stable marriage problem, $f_v$ is the "stability" of the vertex $v$; it is $0$ if $v$ is incident to an unstable edge (blocking edge) and $1$ otherwise. Then the objective is to find a matching that maximises $\sum_v f_v$. (And this can be solved by using the Gale–Shapley algorithm; the optimum is always $|V|$.)

A crucial property of this $f_v$ is that it depends not only on which edges incident to $v$ are matched, but also on the neighbours of the edges incident to $v$.

(Edit: The above property is essential in order to get something that isn't just the maximum-weight matching problem in disguise. Note that if feasible solutions are matchings and if $f_v$ only depends on which edges incident to $v$ are matched, then we can define the weight $w(e)$ of an edge $e = \{u,v\}$ as follows: how much $f_u + f_v$ increases if we replace an empty matching $M = \emptyset$ by a matching $M' = \{e\}$ that contains just the edge $e$. A maximum-weight matching w.r.t. these weights also maximises $\sum_v f_v$.)

Answer 6

Many variants and generalizations are considered in the book by Lovasz and Plummer.