Complexity of a graph parity-coloring problem

Question

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?

Answer 1

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 minimum weight version is named min-cost T-join that is studied in this note, which is an application of min-cost matching.

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.

---

If the graph is a tree, the solution is much simpler as Yuval Filmus pointed out in the comment.

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.

Note for a tree, there is at most one feasible solution. So asking for maximum/minimum weight may be meaningless.