<p>Maximum weight matching on $G$ is equivalent to maximum weight independent set on <a href="http://en.wikipedia.org/wiki/Line_graph" rel="noreferrer">line-graph</a> of $G$, and can be written as follows</p>

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

<p>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</p>

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

<p>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</p>

<p>$$\max_{\mathbf{x}} \prod_{e \in E} f_{e}(x_e)$$</p>

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

<p>Example:</p>

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

<p>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 </p>

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

<p>See [<a href="http://www.ics.uci.edu/~dechter/publications/r177.html" rel="noreferrer">Flerova,2010</a>] for meaning of objective above.</p>

<p>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</p>

<p>$$\bigoplus_x \bigotimes_e f_e(x)$$</p>

<p>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</p>

<p>Examples:</p>

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

<p>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" [<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.125.8954&amp;rep=rep1&amp;type=pdf" rel="noreferrer">Aji, 2000</a>], which works in $O(1)$ time for bounded tree-width hypergraphs.</p>

<p>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)</p>

CC BY-SA 2.5
2010-11-07T03:30:09.220Z
2010-11-07T03:30:09.220Z
Yaroslav Bulatov
<p>There are several extensions of the problem to more general structures.  For instance:</p>
<ul>
<li><p>Matroid matching (<a href="https://math.mit.edu/%7Egoemans/18997-CO/co-lec15.ps" rel="nofollow noreferrer">lecture notes</a>, <a href="https://doi.org/10.1016/0095-8956(80)90066-0" rel="nofollow noreferrer">Matroid matching and some applications</a>, <a href="https://theory.stanford.edu/%7Ejvondrak/data/matroid-parity-STOC.pdf" rel="nofollow noreferrer">Matroid Matching: the Power of Local Search</a>)</p>
</li>
<li><p>Path-matching (<a href="https://doi.org/10.1007/BF01758837" rel="nofollow noreferrer">Path-matching problems</a>, <a href="https://doi.org/10.1007/s101070100256" rel="nofollow noreferrer">Matching, matroids, and extensions</a>)</p>
</li>
<li><p>Hypergraph matching (Can't find any good references)</p>
</li>
</ul>
<p>Generally, these extensions are NP-hard.</p>

CC BY-SA 2.5
2010-08-30T23:45:12.130Z
whats a good example of a bunch which aren't intractable?
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-31T01:27:22.210Z
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
CC BY-SA 4.0
2010-08-30T08:19:59.283Z
2022-10-09T10:13:51.343Z
2022-10-09T10:13:51.343Z
Ian
<p>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, <a href="http://en.wikipedia.org/wiki/Earth_mover%27s_distance" rel="nofollow">the earth-mover distance</a>, the Monge-Kantorovich-Wasserstein distance, or the Mallows distance, depending on who you ask). </p>

CC BY-SA 2.5
2010-08-29T21:07:05.140Z
2010-08-29T21:07:05.140Z
Suresh Venkat
<p>If you want something that <em>cannot</em> be easily reduced to the maximum-weight matching problem, here is one example: the <a href="http://mathworld.wolfram.com/StableMarriageProblem.html" rel="nofollow">stable marriage problem</a>.</p>

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

<p>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 <em>neighbours</em> of the edges incident to $v$.</p>

<p>(<em>Edit:</em> 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$.)</p>

CC BY-SA 2.5
2010-08-30T00:40:09.167Z
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
CC BY-SA 2.5
2010-08-30T00:40:28.260Z
and w(e_v) is the weight of the edge e_v of course
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-30T08:38:47.013Z
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
CC BY-SA 2.5
2010-08-30T18:16:12.063Z
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
CC BY-SA 2.5
2010-08-30T19:26:35.270Z
@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
CC BY-SA 2.5
2010-08-31T03:09:03.817Z
hehe, actually you can get both if you use my proposed utilities via the linear programming approach to computing a maximum weight matching :)
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-31T03:13:18.740Z
that approach entrails assigning each edge a variable $e_i$, then for each vertex $v$, have the constraint $0 \leq \sum_{i\in E(v)} e_i \leq 1$, and then have the linear objective be $\sum_v f_v$ where $f_v = \sum_{e\in E(v)} e_i \cdot f_v (e_i)$
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-31T03:13:50.503Z
i'll think about it more after some sleep
Carter Tazio Schonwald
CC BY-SA 2.5
2010-08-29T23:06:39.000Z
2010-08-30T19:37:24.440Z
2010-08-30T19:37:24.440Z
Jukka Suomela
<p>Yet another classical problem that can be interpreted as a matching problem with a strange objective function $f_v$ is <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node21.html" rel="nofollow">minimum maximal matching</a>.</p>

<p>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.</p>

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

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

CC BY-SA 2.5
2010-08-30T19:56:44.513Z
I'm wondering if this question should be CW; it seems that one can generate arbitrarily many examples along these lines.
Jukka Suomela
CC BY-SA 2.5
2010-08-30T19:55:11.090Z
2010-08-30T19:55:11.090Z
Jukka Suomela
<p>Many variants and generalizations are considered in <a href="http://rads.stackoverflow.com/amzn/click/0444879161" rel="nofollow">the book by Lovasz and Plummer</a>.</p>

CC BY-SA 2.5
2010-11-06T19:47:37.137Z
2010-11-06T19:47:37.137Z
h.a
<p>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.</p>

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

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

<p>Have other variants been studied that are generalizations in a different way?</p>

<p>pleas provide references if applicable!</p>

CC BY-SA 2.5
2010-08-30T08:29:24.007Z
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
CC BY-SA 2.5
2010-08-30T18:18:50.480Z
The former, I'm interested in different objective functions.
Carter Tazio Schonwald
<ds.algorithms><graph-theory>
Have any generalizations of maximum weight matching been studied?
Carter Tazio Schonwald
# Have any generalizations of maximum weight matching been studied?

(Asked by: username_0 on 2010-08-29)

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!

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_1**: 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)?  
> **username_0**: The former, I'm interested in different objective functions.  

---

## 6 answers

### Answer by username_2 on 2010-11-07. Score: 6 | Accepted answer

Maximum weight matching on $G$ is equivalent to maximum weight independent set on [line-graph](http://en.wikipedia.org/wiki/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](http://www.ics.uci.edu/~dechter/publications/r177.html)] 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.125.8954&rep=rep1&type=pdf)], 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 by username_3 on 2010-08-30. Score: 9

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

* Matroid matching ([lecture notes](https://math.mit.edu/%7Egoemans/18997-CO/co-lec15.ps), [Matroid matching and some applications](https://doi.org/10.1016/0095-8956(80)90066-0), [Matroid Matching: the Power of Local Search](https://theory.stanford.edu/%7Ejvondrak/data/matroid-parity-STOC.pdf))
* Path-matching ([Path-matching problems](https://doi.org/10.1007/BF01758837), [Matching, matroids, and extensions](https://doi.org/10.1007/s101070100256))
* Hypergraph matching (Can't find any good references)

Generally, these extensions are NP-hard.

> **Comments:**
> **username_0**: whats a good example of a bunch which aren't intractable?  
> **username_3**: 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).  

---

### Answer by username_4 on 2010-08-29. Score: 7

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](http://en.wikipedia.org/wiki/Earth_mover%27s_distance), the Monge-Kantorovich-Wasserstein distance, or the Mallows distance, depending on who you ask).


---

### Answer by username_1 on 2010-08-30. Score: 5

Yet another classical problem that can be interpreted as a matching problem with a strange objective function $f\_v$ is [minimum maximal matching](http://www.nada.kth.se/~viggo/wwwcompendium/node21.html).

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

> **Comments:**
> **username_1**: I'm wondering if this question should be CW; it seems that one can generate arbitrarily many examples along these lines.  

---

### Answer by username_1 on 2010-08-29. Score: 4

If you want something that *cannot* be easily reduced to the maximum-weight matching problem, here is one example: the [stable marriage problem](http://mathworld.wolfram.com/StableMarriageProblem.html).

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

> **Comments:**
> **username_0**: 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.  
> **username_0**: and w(e_v) is the weight of the edge e_v of course  
> **username_1**: 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.  
> **username_0**: 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  
> **username_1**: @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.  
> **username_0**: hehe, actually you can get both if you use my proposed utilities via the linear programming approach to computing a maximum weight matching :)  
> **username_0**: that approach entrails assigning each edge a variable $e_i$, then for each vertex $v$, have the constraint $0 \leq \sum_{i\in E(v)} e_i \leq 1$, and then have the linear objective be $\sum_v f_v$ where $f_v = \sum_{e\in E(v)} e_i \cdot f_v (e_i)$  
> **username_0**: i'll think about it more after some sleep  

---

### Answer by username_5 on 2010-11-06. Score: 2

Many variants and generalizations are considered in [the book by Lovasz and Plummer](http://rads.stackoverflow.com/amzn/click/0444879161).


---

