While getting through Algorithm Design Manual (by Skiena) I have faced the minimum weight vertex cover problem. Though I am aware of the DP solution for this problem algorist.com states another one through two coloring technique. It states the following:
We know we will be able to remove at most one every other node, so we use a two-coloring technique (Red/Black) and perform a post-order traversal. Let's assume we will remove all the Black node. When we process a node, we also store with each node the sum over its immediate children of the respective Red and Black weight for the subtree. If not all of the children are Red, we need to mark the current node as Red. But we also have the option to reverse the coloring of all the Red-children's subtree. So we look at the sum over the red-children for Red and Black, and compare the difference of these sum to the current node's weight. If the current node's weight is above, we swap the coloring for these subtree. The current node will record the Black and Red sum of its children's subtree, and add its own weight to its color.
Can anyone, please, rephrase what is written in the solution, since I can't exactly figure out the condition of switching the colors and I have read it quite many times.
Thanks.
