<p>The problem is polynomial time solvable.</p>

<p>After discussing with <a href="http://vmadan2.web.engr.illinois.edu/" rel="nofollow noreferrer">Vivek Madan</a>, we can show that the proof of Theorem 5.1 in <a href="https://eccc.weizmann.ac.il/report/2010/201/" rel="nofollow noreferrer">Perfect Matching in Bipartite Planar Graphs is in UL</a> works in the weighted context too (their result is to decide if there is a feasible solution). </p>

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

<p>Claim: <span class="math-container">$M\triangle C$</span> is a minimum weight even red edge perfect matching.</p>

<p>The problem reduces to finding an alternating cycle that contains an odd number of red edges. </p>

<p>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. 
<del>For general graphs, a similar approach works, but the reduction is a little more involved.</del> We actually don't know how to do it for general graphs.</p>

<p>Note the bipartite graph case actually follows from a more general theorem. Here we directly quote the following problem from <a href="https://dl.acm.org/citation.cfm?id=3055473" rel="nofollow noreferrer">Artmann, Weismantel, Zenklusen 17</a></p>

<blockquote>
  <p><strong>Parity TU-optimization</strong></p>
  
  <p>Given a totally unimodular matrix <span class="math-container">$T$</span> with <span class="math-container">$rank(T)=n$</span>, <span class="math-container">$b\in
&gt; \mathbb{Z}^m,c\in \mathbb{Z}^n,\alpha\in \{0,1\}$</span> and <span class="math-container">$S\subset [n]$</span>.
  solve 
  <span class="math-container">$$\max\{c^T x: Tx\leq b, x\in \mathbb{Z}^n_{\geq 0}, x(S)\equiv \alpha \pmod 2\}$$</span></p>
</blockquote>

<p>Parity TU-optimization can be solved in polynomial time, and the bipartite case of our problem reduces to it. (Note the <span class="math-container">$rank(T)=n$</span> is easily satisfied by requiring <span class="math-container">$x_i\geq 0$</span> for all <span class="math-container">$i$</span>).</p>

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

CC BY-SA 4.0
2018-08-12T06:16:27.453Z
2018-10-22T15:42:22.793Z
2018-10-22T15:42:22.793Z
Chao Xu
<p>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 <a href="https://doi.org/10.1016/j.ipl.2003.09.016" rel="noreferrer">https://doi.org/10.1016/j.ipl.2003.09.016</a> . </p>

<p>In randomized polynomial time, you can determine whether there is a perfect matching whose weight is <em>exactly</em> 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. </p>

<p>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.</p>

CC BY-SA 4.0
2018-08-12T06:19:05.303Z
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
CC BY-SA 4.0
2018-08-09T08:15:52.167Z
2018-08-09T08:15:52.167Z
Bart Jansen
<p>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. </p>

<p>Is this problem solvable in polynomial time? Even for bipartite graphs?</p>

<p>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.</p>

<matching>
Min weight perfect matching with even number of red edges
Chao Xu
# Min weight perfect matching with even number of red edges

(Asked by: username_0 on 2018-08-09)

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.

**Tags:** matching


---

## 2 answers

### Answer by username_0 on 2018-08-12. Score: 5 | Accepted answer

The problem is polynomial time solvable.

After discussing with [Vivek Madan](http://vmadan2.web.engr.illinois.edu/), we can show that the proof of Theorem 5.1 in [Perfect Matching in Bipartite Planar Graphs is in UL](https://eccc.weizmann.ac.il/report/2010/201/) 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](https://dl.acm.org/citation.cfm?id=3055473)

> **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.


---

### Answer by username_1 on 2018-08-09. Score: 12

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.

> **Comments:**
> **username_0**: 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.  

---

