Exact matching

The matching problem is one of the most widely studied problems in complexity theory and combinatorial optimization. A blue-red graph is a graph with each of its edges coloured either red or blue. Given a parameter k, the exact matching problem asks for a perfect matching with exactly k red edges in a blue-red graph. We survey the exact matching problem, one of the lesser understood problems in the class of matching problems. We also propose an additive approximation of the problem which gives a matching with n − 1 edges with exactly k red edges for a graph with 2n vertices, or correctly asserts that no perfect matching with exactly k red edges exists in the graph.