Moreover, only a direct child of c can choose v as a parent instead of c (Figure 4b), because for any other descendant of c, v would become a second parent, and G red will no longer be a directed forest (Figure 4b').
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.