Consider a weighted graph with some red edges. We are interested in finding a perfect matching, such that the number of red edges is even, and under the previous constraints, the weight is minimized.

Is this problem solvable in polynomial time? Even for bipartite graphs?

What about a natural extension. The case where there is a constant number of colors, and the number of edges of each color in the matching must be even.

I think your problem is solvable in randomized polynomial time, if the weights are bounded polynomially in the size of the graph. You can use an approach based on the algebraic matching algorithm by Mulmuley, Vazirani, and Vazirani. It has been useful for similar applications in the past, see for example Proposition 9 and the preceding discussion in Daniel Marx's paper https://doi.org/10.1016/j.ipl.2003.09.016 .

In randomized polynomial time, you can determine whether there is a perfect matching whose weight is exactly a prescribed value, in an integer-weighted graph with weights bounded polynomially in the graph size. Now, say your graph has $n$ vertices and the maximum weight is $W$. Re-weight the red edges of the graph as follows: if the original weight was x, the new weight becomes $(nW+1) + x$. (I also assume all weights are nonnegative, which can easily be done by adding the same constant value to all of them.) Then observe the following: any perfect matching in the re-weighted graph whose total weight is in the interval $[0 ... nW]$, is a perfect matching with 0 red edges. If its total weight is in the interval $[2(nW+1) ... 2(nW+1) + nW]$, then it is a perfect matching with exactly 2 red edges. In general, from the weight range you can infer the number of red edges.

Hence to find a minimum-weight matching with an even number of red edges, it suffices to go over all the weight ranges corresponding to matchings with an even number of red edges, testing for each weight in that range whether there is a perfect matching of that weight, and scaling the weight of each re-weighted matching back based on the number of red edges contained in it, to figure out which of these corresponds to the minimum-weight even-red perfect matching in your original graph. By standard self-reduction techniques, you can then also extract the matching itself rather than just the value, but you might have to boost the success probability by doing multiple trials to get an overall good success probability when doing self-reduction.

  • 2
    Thanks. This seems to also work for the more general case where the number of colors is constant, and each color needs to show up even number of times in the matching. – Chao Xu Aug 12 at 6:19

The problem is polynomial time solvable for bipartite graphs.

After discussing with Vivek Madan, we can show that the proof of Theorem 5.1 in Perfect Matching in Bipartite Planar Graphs is in UL works in the weighted context too (their result is to decide if there is a feasible solution).

Let $R$ be the set of even edges. Let $M$ be a minimum weight perfect matching. If $|M\cap R|$ is even, then we are done. Otherwise, let $C$ be an $M$-alternating cycle such that $|C\cap R|$ is odd, and it is the $M$-alternating cycle with this property such that it minimizes the weight of $M\triangle C$.

Claim: $M\triangle C$ is a minimum weight even red edge perfect matching.

The problem reduces to finding an alternating cycle that contains an odd number of red edges. For bipartite graphs, the problem is easy, since it can be reduced to finding a minimum weight odd cycle in a directed graph with no negative cycles. Which seems to be solvable in polynomial time by various accounts (but I cannot find a concrete citation). A Floyd-Warshall like algorithm is sufficient.

We have no idea about the case where there is a constant number of colors.

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.