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

• Hi ! What would be the idea of your reduction to 3-matching, with no color limit ? Mar 2 at 14:30
• @HugoManet Perhaps Good question, I should clarify "multiple colors". When there are $n$ colors, I allow exactly $n$ edges between any two $x, y$. Mar 3 at 0:06
• @HugoManet That said, here's my informal argument idea: 1. Input: A tripartite hyper-graph $G = (X, Y, Z), E \subset X \times Y \times Z$. 2. Label each vertex in $Y$ with a distinct color. 3. Contract every edge $e \in E$; if there's a path from $x \rightarrow y \rightarrow z$, contract the edge to be an edge $x \rightarrow z$ and color this edge the same color as $y$. 4. Set weights in present edges to be $1$ and all others to be $0$. 5. Run the algorithm over contracted graph and the maximum weight matching is a 3 dimensional-matching (NP-Complete). Mar 3 at 0:07
• cstheory.stackexchange.com/q/48595/5038
– D.W.
Mar 17 at 0:25

The idea would be to solve simultaneously the problem for every constraint of $$(r,b)$$, using almost classical algorithms. But the augmenting paths you find in one instance don't necessarily impact that instance, but the neighboring instances instead, because the augmenting path might impact the $$(r,b)$$ balance.
With $$k$$ different colors, by counting the number of weak composition, you would have $$n+k-1 \choose k-1$$ such instances to consider, which is compatible with the NP-completeness reduction you found for $$k = n$$.
• Which elementary algorithms would you suggest using? Also, I believe this would be polynomial only if the constraints on red and black edges is binding. If the constraints are $\leq r$ and $\leq b$, then does what you have in mind work still? Mar 7 at 5:49