Complexity of finding a matching with color constraints in an edge-colored graph with only 2 colors. Problem
The problem I am considering is the following:
Given: A (multi-)graph $G = (V, E)$ in which each edge is colored either red or blue, and two integers $r$ and $b$.
Determine: Whether a perfect matching $M$ exists in $G$ with exactly $r$ red edges and exactly $b$ blue edges.
For additional context: any graph admitting such a matching will of course have an even number of vertices $n$ (otherwise no perfect matching can exist) and it must hold that $r+b = n/2$ (otherwise the color constraints cannot be satisfied).
I am interested in the complexity of the above problem, primarily whether or not the problem is NP-hard.
Motivation
I am researching a different graph problem for my thesis and have rewritten an interesting case distinction into a form where it is generalized by the problem described above. This problem seemed much more fundamental than my original one, but I was not able to find any literature on it. The closest I could find was Lemma 3.2 in this paper by Dániel Marx.
What I would be interested in is insights or literature on this problem or similar problems. Eventually I am also interested in the problem generalized to more than two colors, but any information on the 2-color would already be very much appreciated.
 A: This is usually called the exact perfect matching problem. It was posed in the paper The Complexity of Restricted Spanning Tree Problems by Papadimitriou and Yannakakis, and the paper Matching is as Easy as Matrix Inversion by Mulmuley, Vazirani, and Vazirani gives a randomized polynomial-time algorithm. It does not appear that a deterministic polynomial-time algorithm is known. You should read the paper for full details, but I will summarize.
The idea is based on the Tutte matrix of $G$. This matrix is defined by $$A_{ij} = \begin{cases} x_{ij} & \mbox{if}\;(i,j) \in E \mbox{ and } i<j\\
-x_{ji} & \mbox{if}\;(i,j) \in E \mbox{ and } i>j\\
0 & \mbox{otherwise} \end{cases}$$
The determinant of $A$ is a polynomial in $|E(G)|$ variables; because $A$ is skew-symmetric, it is the square of the Pfaffian of $A$. Every term in the Pfaffian corresponds to a perfect matching in $G$; specifically, for a matching $M$, we get a term $\pm \prod_{e \in M} x_e$.
Finding the determinant of the Tutte matrix in terms of all the $|E(G)|$ variables is difficult, but substituting values for each $x_e$ and evaluating the determinant numerically is easy. This gives a randomized algorithm for seeing if $G$ has a perfect matching: plug in random values for each $x_e$, and see if the determinant is $0$.
(Carefully chosen ways to plug in random values give guarantees about how well this will work; it isn't foolproof because multiple matchings might cancel to give us a determinant of $0$.)
For the exact perfect matching problem, we modify the Tutte matrix: for every red edge $ij$, we multiply $x_{ij}$ by $y$. Now a matching $M$ with $r$ red edges corresponds to a term $\pm y^r \prod_{e \in M}x_e$ in the Pfaffian, and to solve the problem, we must determine if the coefficient of $y^r$ in the Pfaffian is nonzero.
If we plug in random values for the $x_e$, this gives a polynomial in $y$. We can't find this polynomial by a direct computation of the determinant, but with only one variable involved, we can do almost as well. Pick random values for $x_e$ and try them with $n+1$ different values of $y$. This evaluates the degree-$n$ polynomial at $n+1$ points, and we can interpolate to find the polynomial - and see what the coefficient of $y^r$ is.
Again, getting a coefficient of $0$ does not guarantee there is no exact matching: it's possible that we plugged in the wrong $x$-values and several matchings canceled. But a lemma of Mulmuley, Vazirani, and Vazirani gives us a way to guarantee that when there is an exact matching, we get a nonzero coefficient with some reasonable probability (assuming the random values are picked correctly). Repeat enough times, and we can be confident of the answer.
