# Adding Edges for Maximizing Weighted Reachability +
## 4 Polynomial-Time Algorithm for Trees
### Binary Trees  
In the following, we introduce our dynamic-programming algorithm to solve the MCI problem in binary trees. Let us consider an instance of the MCI problem with a directed weighted binary tree \(T=(V,E)\), where all the edges are directed towards the leaves, the root \(r\in V\) is the only source node, and \(w:V\to\mathbb{N}_{\geq 0},\ p:V\to\mathbb{N}_{\geq 0}\). Let us denote by \(\psi(v)\) (left child) and \(\delta(v)\) (right child) the children of node \(v\in T\); moreover, we denote as \(T(v)\) the sub-tree rooted at \(v\). Let us first note that given a node \(v\), and given a solution \(S_{v}\) that connects some leaves of \(T(v)\) to \(r\). The _gain_ of solution \(S_{v}\) in \(T(v)\) is simply the increase in weighted reachability of some of the nodes in \(T(v)\) that can be written as \(\sum_{u\in T(v)}w_{u}(p(T(u,S_{v}))-p(T(u)))\). Note that, given a node \(u\in T(v)\), if in the subtree of \(u\) is not present one of the edges of \(S_{v}\), then the value \(p(T(u,S_{v}))-p(T(u))\) is equal to zero since \(T(u,S_{v})=T(u)\). On the other hand, if at least one edge is present, then, \(T(u,S_{v})=T(r)\)  
The algorithm that we propose computes a solution that connects \(b\) leaves of \(T(v)\) to \(r\) and maximises the gain in \(T(v)\) for each node \(v\in V\) and for each budget \(b=0,1,\ldots,B\). Formally, we define \(g(v,b)\) as the maximum gain in \(T(v)\) achievable by adding at most \(b\) edges from \(b\) leaves of \(T(v)\) to node \(r\). Note that \(g(v,1)\leq g(v,2)\leq\ldots\leq g(v,b)\). We then now show how to compute \(g(v,b)\) for each node \(v\) and for each budget \(b=0,1,\ldots,B\) by using a dynamic programming approach. For each leaf \(v\in T\) and for each \(b=1,2,\ldots,B\), we have that \(g(v,b)=w_{v}\cdot(p(T(r))-p(T(v)))\), that is, the sum of profits \(p\) of the new nodes that \(v\) can reach thanks to the new edge \((v,r)\). Moreover \(g(v,0)=0\) for each \(v\in V\). Then, the algorithm visits the nodes in \(T\) in post order. For each internal node \(v\) we compute \(g(v,b)\) by using the solutions of its sub-trees, i.e., \(T(\psi(v))\) and \(T(\delta(v))\). Let us assume that we have computed \(g(\psi(v),b)\) and \(g(\delta(v),b)\), for each \(b=0,1,\ldots,B\). Recall that, if a solution adds an edge between any leaf of \(T(v)\) and \(r\), then the gain of node \(v\) is \(w_{v}(p(T(r))-p(T(v)))\) since \(v\) now reach all the nodes in \(T\). This gain is independent of the number of edges that are added from the leaves of \(T(v)\) to \(r\). In fact, given \(g(\psi(v),b_{l})\) as the maximum gain for \(T(\psi(v))\) and budget \(b_{l}\in\{1,2,\ldots,B\}\), the gain in \(T(v)\) of a solution that connects \(b_{l}\) leaves of \(T(\psi(v))\) to \(r\) is equal to \(g(\psi(v),b_{l})+w_{v}\cdot(p(T(r))-p(T(v)))\). Similarly, the gain in \(T(v)\) of the solution that connects, for some \(b_{r}\in\{1,2,\ldots,B\}\), \(b_{r}\) leaves of \(T(\delta(v))\) to \(r\) is equal to \(g(\delta(v),b_{r})+w_{v}\cdot p(T(r))-p(T(v))\). Then, once we have decided how many edges to add in \(\psi(v)\) and in \(\delta(v)\) for \(g(v,b)\), we increase the reachability function of the same quantity, i.e., \(w_{v}\cdot(p(T(r))-p(T(v)))\). Hence, \(g(v,b)\) is given by the combination of \(b_{l}\) and \(b_{r}\) such that the sum is equal to the considered budget, i.e., \(b_{l}+b_{r}=b\), that maximises the sum \(g(\psi(v),b_{l})+g(\delta(v),b_{r})+w_{v}\cdot(p(T(r))-p(T(v)))\). Precisely:  
\[g(v,b)=\max_{ \begin{subarray}{c}b_{l},b\in\{0,\dots,b\}\\ b_{l}+b_{r}=b\end{subarray} }\{g(\psi(v),b_{l})+g(\delta(v),b_{r})\}+w_{v}\cdot( p(T(r))-p(T(v))). \tag{1}\]  
The optimal value of the problem \(f(S)=g(r,B)+f(T)\), where \(f(T)\) is the value of the objective function on \(T\) (i.e., when no edges have been added). The pseudo-code of the algorithm is reported in Algorithm 1.