<p>Your problem is closely related to the so-called <strong>&quot;Exact red-blue bipartite matching&quot;</strong> problem, see for instance <a href="http://lemon.cs.elte.hu/egres/open/Exact_matching_in_red-blue_bipartite_graphs" rel="nofollow noreferrer">http://lemon.cs.elte.hu/egres/open/Exact_matching_in_red-blue_bipartite_graphs</a>.</p>
<ul>
<li><p>The case with two colors is unlikely to be NP-hard, since it is known to belong to RNC<span class="math-container">$^2$</span>.
I think that this randomized result can be translated to your problem.</p>
</li>
<li><p>The case where the number of colors is part of the input is NP-hard,
and this hardness argument easily transfers to your problem.</p>
</li>
</ul>

CC BY-SA 4.0
2021-03-16T21:06:53.780Z
Wow, thank you so much. Something like this is exactly what I was looking for. I will study these deeper. Do you happen to know how these sorts of techniques can be extended to weighted graphs?
arealguru
CC BY-SA 4.0
2021-03-16T11:32:11.457Z
2021-03-16T11:32:11.457Z
Gamow
<p>Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.</p>
<p>Consider a multi-edge bipartite graph <span class="math-container">$G = (L, R, E)$</span>, with <span class="math-container">$|L| = |R| = n$</span>, such that any <span class="math-container">$x \in L, y \in R$</span> have precisely two edges in <span class="math-container">$E$</span>, <span class="math-container">$(x, y)_r, (x,y)_b$</span>. We can imagine that we are assigning these edges a &quot;color&quot;. Given that each edge <span class="math-container">$e \in E$</span> has a weight assigned to it <span class="math-container">$w(e)$</span>, is it possible to find the maximum weight matching in this graph, subject to constraints on the number of <span class="math-container">$\leq r$</span> edges and <span class="math-container">$\leq b$</span> edges?</p>
<p>I believe I have a proof that this problem is NP hard (reduction to 3-matching) when I can freely adjust the number of colors, but in the case of two colors, I haven't been able to find anything. I've been searching for the past couple of days for any existing literature on similar problems with no avail. I would appreciate any suggestions or directions in moving forward.</p>
<p>Some ideas I've tested have included reductions to <a href="https://www.sciencedirect.com/science/article/pii/S0166218X1000435X" rel="nofollow noreferrer">flow/matching problems with disjunctive constraints.</a></p>
<p>When I posted this question on <a href="http://mathoverflow.net/q/385349/37212">Math Overflow</a>, I received help from an individual who believed this problem was not NP. He suggested I look into path augmenting algorithms like Ford-Fulkerson, but unfortunately I have not found this to work; the idea of &quot;backwards&quot; flow doesn't make much sense when working with a color constraint.</p>

CC BY-SA 4.0
2021-03-17T00:25:43.130Z
We ask you to link to the other copies, and to maintain each copy, in this case, by summarizing the answers you've already received on MO.  https://mathoverflow.net/q/385349/37212
D.W.
<graph-theory><graph-algorithms><co.combinatorics><optimization><matching>
Maximum weight matching with classes of edges in a multi-edge bipartite graph
arealguru
# Maximum weight matching with classes of edges in a multi-edge bipartite graph

(Asked by: username_0 on 2021-03-16)

Posted a similar question in mathoverflow, have tried to reduce this to Ford Fulkerson, but been stuck. Thought I'd ask TCS community to see if there are any ideas from individuals, here.

Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)\_r, (x,y)\_b$. We can imagine that we are assigning these edges a "color". Given that each edge $e \in E$ has a weight assigned to it $w(e)$, is it possible to find the maximum weight matching in this graph, subject to constraints on the number of $\leq r$ edges and $\leq b$ edges?

I believe I have a proof that this problem is NP hard (reduction to 3-matching) when I can freely adjust the number of colors, but in the case of two colors, I haven't been able to find anything. I've been searching for the past couple of days for any existing literature on similar problems with no avail. I would appreciate any suggestions or directions in moving forward.

Some ideas I've tested have included reductions to [flow/matching problems with disjunctive constraints.](https://www.sciencedirect.com/science/article/pii/S0166218X1000435X)

When I posted this question on [Math Overflow](http://mathoverflow.net/q/385349/37212), I received help from an individual who believed this problem was not NP. He suggested I look into path augmenting algorithms like Ford-Fulkerson, but unfortunately I have not found this to work; the idea of "backwards" flow doesn't make much sense when working with a color constraint.

**Tags:** graph-theory, graph-algorithms, co.combinatorics, optimization, matching
> **Comments:**
> **username_1**: We ask you to link to the other copies, and to maintain each copy, in this case, by summarizing the answers you've already received on MO.  https://mathoverflow.net/q/385349/37212  

---

## 1 answers

### Answer by username_2 on 2021-03-16. Score: 1 | Accepted answer

Your problem is closely related to the so-called **"Exact red-blue bipartite matching"** problem, see for instance <http://lemon.cs.elte.hu/egres/open/Exact_matching_in_red-blue_bipartite_graphs>.

* The case with two colors is unlikely to be NP-hard, since it is known to belong to RNC$^2$.
  I think that this randomized result can be translated to your problem.
* The case where the number of colors is part of the input is NP-hard,
  and this hardness argument easily transfers to your problem.

> **Comments:**
> **username_0**: Wow, thank you so much. Something like this is exactly what I was looking for. I will study these deeper. Do you happen to know how these sorts of techniques can be extended to weighted graphs?  

---

