# Adding Edges for Maximizing Weighted Reachability +
## 4 Polynomial-Time Algorithm for Trees
### Binary Trees
```
Input :\(T=(V,E)\), \(B\), \(w_{v}\), \(p_{v}\)\(\forall v\in V\) Output :Set \(S\) of edges
1 foreach node \(v\)do
2\(g(v,0):=0\)
3\(S_{(v,b)}:=\emptyset\)
4 foreach leaf \(v\) and budget \(b\), with \(\{1,\dots,B\}\)do
5\(g(v,b):=w_{v}\cdot(p(T(r))-p(T(v)))\)
6\(S_{(v,b)}:=\{(v,r)\}\)
7 foreach node \(v\) in post-orderingdo
8 for\(b\in 1,\dots,B\)do
9\(g(v,b):=\max_{ \begin{subarray}{c}b_{l},b_{r}\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)))\)
10 /* Let \(b_{l}\) and \(b_{r}\) the budgets that maximise Line 9 */ \(S_{(v,b)}:=S_{(\psi(v),b_{l})}\cup S_{(\delta(v),b_{r})}\)
11\(S:=S_{(r,B)}\)
```  
**Algorithm 1**Dynamic programming algorithm for MCI. As a running example, let us consider a binary tree \(T=(V,E)\) composed by eight nodes, as depicted in Figure 2, with \(p_{v}=1\) for any node \(v\in V\) and \(w_{v}=1\) for any node \(v\in V\setminus\{c,e\}\), finally \(w_{c}=w_{e}=2\). If we consider to have budget \(B=2\) and to run Algorithm 1, we first have that any leaf in \(v\in T\) has \(g(v,1)=g(v,2)=1\cdot(p(T(a))-p(T(v)))=7\). Then we start considering the rest of the nodes in post-order, thus we have: \(g(d,2)=14+1\cdot(p(T(a)-T(d))=19)\), \(g(d,1)=12\), \(g(e,1)=7+2\cdot 6=19\). Now, note that when considering node \(c\) we have that \(\max\left\{g(\psi(c),b_{l})+g(\delta(c),b_{r})\right\}=g(e,1)+g(d,1)\) for any \(b_{l},b_{r}\in\{0,\dots,b\},\ b_{l}+b_{r}=b\), that is, we are considering a solution that had added an edge in the left sub-tree and an edge in the right sub-tree. Finally, \(g(c,2)=g(e,1)+g(d,1)+2\cdot(p(T(a))-p(T(c)))=35\). Figure 2: Consider the node \(c\) with \(w_{c}=2\), \(p_{v}=1\forall v\in V\) and \(B=2\). We have: \(g(d,2)=19\), \(g(d,1)=12\), and \(g(e,1)=7+2(6)=19\). Therefore \(g(c,2)=g(e,1)+g(d,1)+w_{c}\cdot(p(T(a))-p(T(c)))=35\). Theorem 3: _Algorithm 1 finds an optimal solution for MCI if the graph is a binary tree._  
Proof: Let us assume by contradiction that \(v\) and \(b\) are, respectively, the first node and the first budget for which Algorithm 1 computes a non-maximum gain at Line 9 of Algorithm 1, that is \(g(v,b)<g^{*}(v,b)\), where \(g^{*}(v,b)\) is the maximum gain for tree \(T(v)\) and budget \(b\). Let \(S^{*}\) be an optimal solution that achieves \(g^{*}(v,b)\) and let \(S^{*}_{l}\), \(S^{*}_{p}\) be the edges in \(S^{*}\) that starts from leaves in \(T(\psi(v))\) and \(T(\delta(v))\), respectively. Let \(b^{*}_{l}=|S^{*}_{l}|\) and \(b^{*}_{r}=|S^{*}_{l}|\). Then, the gain of the optimal solution \(S^{*}\) is: \(g^{*}(v,b)=g(\psi(v),b^{*}_{l})+g(\delta(v),b^{*}_{r})+w_{v}\cdot(p(T(r))-p(T(v )))\). Since by hypothesis \(g(v,b)\) is the first time for which Algorithm 1 does not find the maximum gain and since the cost \((p(T(r))-p(T(v)))\cdot w_{v}\) does not depend on the edges selected in the left and right sub-trees of \(v\), this implies that at Line 9 Algorithm 1 must select  
\[g(v,b)=g(\psi(v),b^{*}_{l})+g(\delta(v),b^{*}_{r})+(p(T(r))-p(T(v)))\cdot w_{v }=g^{*}(v,b),\]  
thus contradicting \(g(v,b)<g^{*}(v,b)\). For each node \(v\), the algorithm computes \(B+1\) values of function \(g\). Therefore, the variables \(g(v,b)\) can be seen for example as a matrix of dimension \(|V|\times(B+1)\). For each entry of the matrix, we need to compute the maximum among \(B+1\) gains (see Equation (1)) because the number of budgets that we need to try to combine to find the solution is \(\binom{B+2-1}{B}=B+1\). Thus, it follows that Algorithm 1 takes \(\mathcal{O}(|V|B^{2})\) time. Note that \(B\in\mathcal{O}(|V|)\) because we limit the new edges to be of the form leaf-root. Moreover, the space complexity is \(O(|V|B)\).