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.
Mulmuley, Vazirani and Vazirani  showed that there is a randomized (RNC2) 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  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 . Another simpler proof was given by Geerdes and Szabó .
For graphs which can be drawn to a fixed orientable surface Galluccio and Loebl  gave a pseudo-polynomial algorithm using Pfaffian orientations, generalizing the analogous result of Barahona and Pulleyblank  on planar graphs. Bhatnagar et al.  studied the problem of approximately counting the number of matchings with exactly k red edges. Yuster  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.
- 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