# Have any generalizations of maximum weight matching been studied?

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!

• A clarification: Do you want generalisations in the sense that feasible solutions are matchings, but your objective function is different from the usual max-weight matchings (something like the case of stable marriages)? Or generalisations in the sense that feasible solutions are also some kind of generalisations or relaxations of matchings (something like independent sets or fractional matchings)? – Jukka Suomela Aug 30 '10 at 8:29
• The former, I'm interested in different objective functions. – Carter Tazio Schonwald Aug 30 '10 at 18:18
• bonus awesome points for such which evade being NP hard or complete – Carter Tazio Schonwald Aug 30 '10 at 22:32

## 6 Answers

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)

• thanks! this is the sort fo answer I was hoping to get :) – Carter Tazio Schonwald Nov 10 '10 at 5:11

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

Generally, these extensions are NP-hard.

• whats a good example of a bunch which aren't intractable? – Carter Tazio Schonwald Aug 30 '10 at 23:45
• There are some special cases that are not intractable. Matroid matching is solvable for linear matroids (see "Matroid matching and some applications" above), as is path matching for some weighting functions (see "Matching, matroids, and extensions" above). – Ian Aug 31 '10 at 1:27

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).

• cool, i'll look into that bunch. Im going to wait a day before selecting it as an answer in case something else thats cool pops up and merits consideration – Carter Tazio Schonwald Aug 29 '10 at 22:41
• heres an upvote in the mean time – Carter Tazio Schonwald Aug 29 '10 at 22:41

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$.

• I'm wondering if this question should be CW; it seems that one can generate arbitrarily many examples along these lines. – Jukka Suomela Aug 30 '10 at 19:56

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$.)

• could you expand your definition of $f_v$ please? Eg in the maximum weight matching case, i'm using $f_v = w(e_v)$ ($e_v$ is the edge v is assigned) and $f_v = 0$ in the case when v is unmatched. – Carter Tazio Schonwald Aug 30 '10 at 0:40
• and w(e_v) is the weight of the edge e_v of course – Carter Tazio Schonwald Aug 30 '10 at 0:40
• Well, do you know the definition of the stable marriage problem? Usually it is formulated as follows: find a matching $M$ such that there are no "bad edges" $(m,w)$ such that $m$ prefers $w$ to his current partner (if any) and $w$ prefers $m$ to her current partner (if any). Now define $f_v$ as follows: let $f_v = 0$ if $v$ is incident to a "bad edge" and otherwise let $f_v = 1$. A solution is stable iff we have $f_v = 1$ for all nodes. – Jukka Suomela Aug 30 '10 at 8:38
• Jukka, what you actually want is to have the $f_v$ be a function of that person's ranking preference. Eg for any $f_v$ should be a decreasing function of how low in their preference set their current matching is. Perhaps I'm misunderstanding something though – Carter Tazio Schonwald Aug 30 '10 at 18:16
• @Carter: With your definition, if you solve the optimisation problem (which is just a special case of the maximum weight matching problem), you will maximise the "total happiness". But this is not what you want in the stable marriage problem! A stable matching doesn't necessarily maximise total happiness, it maximises the stability of the solution. – Jukka Suomela Aug 30 '10 at 19:26

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