Problem of the month April 2011

Our open problem for the month of April is the exact matching problem, in which we have to find a perfect matching in a graph that contains a given number of red edges, when the edge set of the graph is coloured with red and blue. (Here the term edge-coluring refers to an arbitrary assignment of either of the two colours, instead of an edge-colouring in the context of graph colouring.) An interesting aspect of the problem is that by reduction to the computation of the determinant of a matrix with variables, the problem is known to admit a randomized polynomial algorithm, a deterministic algorithm is however not known to date. For a brief overview of the background, see our original open problem page on exact matching.

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.