# Maximum weight matching with classes of edges in a multi-edge bipartite graph

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.

When I posted this question on Math Overflow, 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.

• 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. mathoverflow.net/q/385349/37212
– D.W.
Commented Mar 17, 2021 at 0:25

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