Thus, this case requires adding in G edges from v to all nodes in c and their ancestors; additionally, for each new child of v, denoted by d ∈ V red , we add edges from all nodes in d and their descendants to v. Crucially, although the number of possible subsets of c's children in G red is exponential, the fact that they are independent trees in G red allows us to go over them one by one, and decide for each one whether it will be a child of v or not, depending on whether S v-in (d) is positive.
the score (9) in this case is: where child(c) are the children of c. Case 2b: Inserting v as a new root in G red .