# Max weighted matching where edge weight depends on the matching

MathOverflow Asked on December 25, 2020

Given a bipartite graph $$G$$, we seek a maximal weighted matching $$E$$. The particularity is below. Once an edge $$e$$ is chosen, the action of choosing $$e$$ adds a negative weight $$w(e,e’)$$ to any other edge $$e’$$ in $$M$$. That is, the edge weight depends on the matching we choose. How to approach this problem? Clearly when $$w(e,e’)=0$$ for any pair of $$(e,e’)$$, the problem degenerates to standard max weight matching.

I'm assuming that by maximal we actually mean maximum.

A rainbow perfect matching in a (not necessarily proper) edge-colored bipartite graph $$G$$ on $$2n$$ vertices is a perfect matching of $$G$$ such that no two edges have the same color.

Let $$G = (V,E)$$ be an edge-colored bipartite graph on $$2n$$ vertices. Let $$w(cdot)$$ be the all-ones function, and define $$w(cdot,cdot)$$ such that $$w(e,e') = 0$$ if $$e,e' in E$$ are a pair of disjoint edges that have different colors; otherwise, $$w(e,e') = -c$$ for any $$c > 0$$. An algorithm that solves your problem outputs $$n$$ if and only if $$G$$ has a rainbow perfect matching.

The rainbow perfect matching problem for bipartite graphs is NP-Complete (see, for example, Theorem 1 in Van Bang Le, Florian Pfender, Complexity results for rainbow matchings, Theoretical Computer Science, Volume 524, 2014).

I don't have a hardness of approximation proof, but I am skeptical that your problem admits a polynomial-time constant-factor approximation algorithm. It seems very close to the quadratic assignment problem, and such problems are hard to approximate in polynomial time within a constant factor in both theory and practice.

Answered by Nathan Lindzey on December 25, 2020

Let binary variable $$x_e$$ indicate whether $$ein M$$. The usual maximum weighted matching problem is to maximize $$sum_e c_e x_e$$ subject to: $$sum_{ein E: vin e} x_e le 1 quad text{for all vin V}$$

To model your variant, introduce nonnegative variable $$y_{e,e'}$$ for each pair $$e of edges, change the objective to maximize $$sum_e c_e x_e + sum_{e, and impose constraints: $$x_e + x_{e'} - 1 le y_{e,e'}$$ Note that $$y_{e,e'}$$ will automatically be integer-valued even without explicitly defining it to be binary.

Answered by RobPratt on December 25, 2020

## Related Questions

### Is there a source in which Demazure’s function $p$ defined in SGA3, exp. XXI, is calculated?

0  Asked on December 15, 2021 by inkspot

### Potential p-norm on tuples of operators

1  Asked on December 15, 2021 by chris-ramsey

### Understanding a quip from Gian-Carlo Rota

5  Asked on December 13, 2021 by william-stagner

### What is Chemlambda? In which ways could it be interesting for a mathematician?

1  Asked on December 13, 2021

### Degree inequality of a polynomial map distinguishing hyperplanes

1  Asked on December 13, 2021

### The inconsistency of Graham Arithmetics plus $forall n, n < g_{64}$

2  Asked on December 13, 2021 by mirco-a-mannucci

### Subgraph induced by negative cycles detected by Bellman-Ford algorithm

0  Asked on December 13, 2021

### How to obtain matrix from summation inverse equation

1  Asked on December 13, 2021 by jdoe2

### Is $arcsin(1/4) / pi$ irrational?

3  Asked on December 13, 2021 by ikp

### A mutliplication for distributive lattices via rowmotion

0  Asked on December 13, 2021

### Tensor product of unit and co-unit in a closed compact category

1  Asked on December 13, 2021 by andi-bauer

### Finite subgroups of $SL_2(mathbb{C})$ arising as a semi-direct product

1  Asked on December 13, 2021 by user45397

### Uniqueness of solutions of Young differential equations

0  Asked on December 13, 2021

### Differentiation under the integral sign for a $L^1$-valued function (shape derivative)

0  Asked on December 13, 2021

### Digraphs with exactly one Eulerian tour

2  Asked on December 13, 2021

### Exactness of completed tensor product of nuclear spaces

1  Asked on December 11, 2021

### An integral with respect to the Haar measure on a unitary group

1  Asked on December 11, 2021

### Best known upper bound for Dedekind zeta function on line $sigma=1$ in the $t$ aspect

0  Asked on December 11, 2021

### Regularity with respect to the Lebesgue measure through dimensions

0  Asked on December 11, 2021 by titouan-vayer

### Reference request on Gentzen’s proof of the consistency of PA

1  Asked on December 11, 2021