2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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 $\endgroup$
    – D.W.
    Commented Mar 17, 2021 at 0:25

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – arealguru
    Commented Mar 16, 2021 at 21:06

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.