Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
The problem is polynomial time solvable.
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.
For general graphs, a similar approach works, but the reduction is a little more involved. We actually don't know how to do it for general graphs.
Note the bipartite graph case actually follows from a more general theorem. Here we directly quote the following problem from Artmann, Weismantel, Zenklusen 17
Parity TU-optimization
Given a totally unimodular matrix $T$ with $rank(T)=n$, $b\in > \mathbb{Z}^m,c\in \mathbb{Z}^n,\alpha\in \{0,1\}$ and $S\subset [n]$. solve $$\max\{c^T x: Tx\leq b, x\in \mathbb{Z}^n_{\geq 0}, x(S)\equiv \alpha \pmod 2\}$$
Parity TU-optimization can be solved in polynomial time, and the bipartite case of our problem reduces to it. (Note the $rank(T)=n$ is easily satisfied by requiring $x_i\geq 0$ for all $i$).
We have no idea about the case where there is a constant number of colors.
