Exact matching in red-blue bipartite graphs

From Egres Open
Jump to: navigation, search

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 (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 [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

  1. ↑ K. Mulmuley, U. V. Vazirani, V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica 7 (1987), 105-113. DOI link. Author link
  2. ↑ 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
  3. ↑ T. Yi, K. G. Murty, C. Spera, Matchings in colored bipartite networks, Discrete Applied Mathematics 121 (2002), 261-277. DOI link
  4. ↑ H.-F. Geerdes, J. Szabó. A unified proof for Karzanov's exact matching theorem, EGRES Quick Proof No. 2011-02
  5. ↑ A. Galluccio, M. Loebl, On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents, Electronic journal of combinatorics 6 (1999), R6. Pdf link
  6. ↑ F. Barahona, W. R. Pulleyblank, Exact arborescences, matchings and cycles, Discrete Appl. Math. 16 (1987) 91-99. DOI link
  7. ↑ 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
  8. ↑ R. Yuster, Almost exact matchings, DOI link, author link
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Exact_matching_in_red-blue_bipartite_graphs&oldid=2044"