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.

2 Answers

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<e'$ of edges, change the objective to maximize $sum_e c_e x_e + sum_{e<e'} w(e,e')y_{e,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

Add your own answers!

Related Questions

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

3  Asked on December 13, 2021 by ikp


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP