5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 12 '18 at 19:34
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 13 '18 at 8:07
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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