# Exact matching in red-blue bipartite graphs

Give an algorithm and/or a good characterization to decide if a red-blue edge-coloured bipartite graph contains a perfect matching with exactly *k* red edges.

## Remarks

Mulmuley, Vazirani and Vazirani ^{[1]} showed that there is a randomized (RNC^{2}) algorithm for the problem, based on computing a coefficient in the determinant of a matrix with indeterminates. This algorithm also works for non-bipartite graphs. Deterministic algorithms were given by Karzanov ^{[2]} for complete graphs and complete bipartite graphs. A simpler proof and a new algorithm for complete bipartite graphs were given by Yi, Murty and Spera ^{[3]}. Another simpler proof was given by Geerdes and Szabó ^{[4]}.

For graphs which can be drawn to a fixed orientable surface Galluccio and Loebl ^{[5]} gave a pseudo-polynomial algorithm using Pfaffian orientations, generalizing the analogous result of Barahona and Pulleyblank ^{[6]} on planar graphs. Bhatnagar et al. ^{[7]} studied the problem of approximately counting the number of matchings with exactly *k* red edges. Yuster ^{[8]} gave a combinatorial polynomial algorithm that either certifies that no matching of size [math]\nu(G)[/math] has exactly *k* red edges, or gives a matching of size [math]\nu(G)-1[/math] containing exactly *k* red edges.

If the number of colours is not restricted and the graph is not necessarily simple, then the analogous problem is NP-complete: 3 dimensional perfect matching on *3n* nodes can be reduced to the problem of finding a multicoloured perfect matching in an *n*-edge-coloured bipartite graph on *2n* nodes.

## References

- ↑ K. Mulmuley, U. V. Vazirani, V. V. Vazirani,
*Matching is as easy as matrix inversion*, Combinatorica 7 (1987), 105-113. DOI link. Author link - ↑ A. V. Karzanov,
*On the maximal matchings of a given weight in complete and complete bipartite graphs*, Kibernetika 1 (1987), 7-11. (English translation in: Cybernetics and Systems Analysis 23 (1987), 8–13). DOI link - ↑ T. Yi, K. G. Murty, C. Spera,
*Matchings in colored bipartite networks*, Discrete Applied Mathematics 121 (2002), 261-277. DOI link - ↑ H.-F. Geerdes, J. Szabó.
*A unified proof for Karzanov's exact matching theorem*, EGRES Quick Proof No. 2011-02 - ↑ A. Galluccio, M. Loebl,
*On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents*, Electronic journal of combinatorics 6 (1999), R6. Pdf link - ↑ F. Barahona, W. R. Pulleyblank,
*Exact arborescences, matchings and cycles*, Discrete Appl. Math. 16 (1987) 91-99. DOI link - ↑ N. Bhatnagar, D. Randall, V.V. Vazirani, E. Vigoda,
*Random Bichromatic Matchings*, Algorithmica 50 (2008), 418-445, [http://dx.doi.org/10.1007/s00453-007-9096-4 DOI link - ↑ R. Yuster,
*Almost exact matchings*, DOI link, author link