# Complexity of a graph parity-coloring problem

Suppose I have a positively weighted (bounded-degree) graph $G$ where each vertex in $G$ is colored either black or white. I'm curious about the complexity of the following problem:

Find a subset $S$ of edges of G of maximal weight, subject to the constraint that any node colored black is incident to an odd number of edges in $S$, and any node colored white is incident to an even number of edges in $S$. The constraint is sort of a $2$-coloring up to parity.

The problem seems hard in general. I'm more interested in the simpler case that $G$ is a tree. In this case, are there any efficient algorithms to determine such a set $S$? Also, does this problem have a name?

• Try solving it on a tree using "dynamic programming" (i.e., recursion). For each subtree, solve the corresponding instances with both colors for the root. – Yuval Filmus Jul 12 '18 at 19:34
• On a tree the solution is very simple – work from the leaves up. Hence your correction (in a deleted comment) to the effect that there are no constraints on leaves is important. – Yuval Filmus Jul 13 '18 at 8:07

Note for each node $v$, there is a one-to-one mapping between the parity of incident edges in $S$ and that of incident edges in $\bar{S}$. This means we can consider the problem with minimum weight equivalently.
The idea is, one can decompose $S$ ($\bar{S}$ in the maximum weight version) into a set of edge-disjoint paths joining black nodes (nodes requiring an odd degree), thus the solution is exactly a min-cost matching of the complete graph induced by black nodes where the cost of edge $(u,v)$ is the length of the shortest path between $u$ and $v$ in the original graph. So this problem can be solved by any algorithm solving min-cost matching.