Talk:Exact matching in red-blue bipartite graphs

Approximate version -- Tamás Király 21:20, 15 September 2011 (UTC)

Maybe the following question is easier:

Given a red-blue bipartite graph on 2n nodes, is it possible in polynomial time to either show that it does not have a perfect matching with k red edges, or find a matching with k-1 red edges and n-k-1 blue edges?

Related 2-budgeted problem -- Tamás Király (talk) 07:54, 30 July 2013 (UTC)

The following related problem is called Blue-Red Matching in the paper Randomized and approximation algorithms for blue-red matching. For a graph G and an integer w, find a maximum matching with at most w red edges and at most w blue edges. The authors show that this also has a randomized polynomial algorithm, and give fast approximation algorithms.

-- Chao Xu (talk) 15:41, 1 April 2018 (UTC)

Is finding a minimum weight exact matching NP-hard?

Re: -- Tamás Király (talk) 09:43, 2 June 2018 (UTC)

If the weights are polynomially bounded, then the randomized algorithm of Mulmuley, Vazirani and Vazirani solves the problem. I am not aware of any result for arbitrary weights.