Skip to main content
removed capitals from title
Link
YCor
  • 63.9k
  • 5
  • 187
  • 286

Maximum Weight Matchingweight matching with Classesclasses of Edgesedges in a Multimulti-Edge Bipartite Graphedge bipartite graph

Source Link

Maximum Weight Matching with Classes of Edges in a Multi-Edge Bipartite Graph

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 $r$ edges and $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.