4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Do I understand correctly that the weight assigned to matching M is sum_{e in M} (sum_{e' in M} w(e,e'))? $\endgroup$ May 28, 2020 at 0:37
  • $\begingroup$ Thank you Louigi. Yes, we can formulate in this way. $\endgroup$
    – lchen
    May 28, 2020 at 9:46

2 Answers 2

0
$\begingroup$

Let binary variable $x_e$ indicate whether $e\in M$. The usual maximum weighted matching problem is to maximize $\sum_e c_e x_e$ subject to: $$\sum_{e\in E: v\in e} x_e \le 1 \quad \text{for all $v\in 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.

$\endgroup$
1
  • $\begingroup$ Thank you Rob. Let me be more specific. I seek answers or references to the following questions: (1) is my problem NP-hard? (2) how to design polynomial algorithm or approximate algorithm with constant factor to solve it? $\endgroup$
    – lchen
    May 22, 2020 at 8:36
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.