# Adding Edges for Maximizing Weighted Reachability +
## 5 Polynomial-Time Algorithm for DAG with a Single Source or a Single Sink
It is worth noting that, in this case, differently from before, the value of \(R^{T}(d,S)\) is always equal to \(V\) by definition since all the nodes reach the sink, on the other hand, the reachability of a node \(v\) does not assume only the values \(V\) or \(R(v)\). This implies that we it is not required to perform any DFS visit of \(G^{T}\) to compute \(f(S\cup\{(d,v)\})\), in fact, the vicinity of any other node depends on the set of added  
Figure 3: Example of transformation from general tree to binary tree. edges and has to be recomputed each time by performing a DFS visit on the augmented graph. Hence, \(f(S\cup\{(d,v)\})=f(S)+\sum_{z\in V}w_{z}\cdot p(R(v,S)\setminus R(d,S))\). Since for computing \(f(S\cup\{(d,v)\})\), we must compute \(|V|\) DFS visits, the overall cost of the Greedy algorithm with a single sink increases by a factor of \(|V|\) with respect to the case of DAG with a single source, thus becoming \(\mathcal{O}(B|V|^{2}|E|)\). Namely, for each edge \(e=(u,r)\in E^{\prime}\), to compute \(f(S\cup\{e\})\) it is required \(\mathcal{O}(|V||E|)\) time to compute \(|V|\) DFS visits in \(G(S)\), one for each node in \(V\), and \(\mathcal{O}(|V|)\) time to update \(R\) and to compute \(\sum_{z\in R^{T}(u,S)}w_{z}(|V|-|R(z,S)|)\). Since there are \(\mathcal{O}(|V|)\) sinks, the computation of the maximum value at Line 4 costs \(\mathcal{O}(|V|^{2}|E|)\) time. Then, since at most \(B\) edges are added, the Greedy algorithm requires \(\mathcal{O}(B|V|^{2}|E|)\). Observe that Algorithm 2 that we have just described in the case of a single source can also be used on trees in place of Algorithm 1. However, the complexity of the Greedy algorithm will be \(\mathcal{O}(|V|^{2}B)\) that is greater than the complexity of Algorithm 1, which is \(\mathcal{O}(|V|^{2})\). To give a lower bound on the approximation ratio of Algorithm 2, we show that the objective function \(f(S)\) is _monotone and submodular_. Recall that, for a ground set \(N\), a function \(z:2^{N}\to\mathbb{R}\) is said to be submodular, if it satisfies the following property of diminishing marginal returns: for any pair of sets \(S\subseteq T\subseteq N\) and for any element \(e\in N\setminus T\), \(z(S\cup\{e\})-z(S)\geq z(T\cup\{e\})-z(T)\). This allows us to apply the result by [PERSON] et al. [28]: Given a finite set \(N\), an integer \(k^{\prime}\), and a real-valued function \(z\) defined on the set of subsets of \(N\), the problem of finding a set \(S\subseteq N\) such that \(|S|\leq k^{\prime}\) and \(z(S)\) is maximum can be \(1-\frac{1}{e}\) approximated by starting with the empty set, and repeatedly adding the element that gives the maximal marginal gain, if \(z\) is monotone and submodular. Recall that \(f(S)=\sum_{v\in V}w_{v}p(R(v,S))\) and \(w_{v},p_{v}\in\mathbb{N}_{\geq 0}\). To prove that \(f(S)\) is a monotone increasing and submodular function, we just need to show that \(p(R(v,S))\) is monotone increasing and submodular, for each node \(v\in V\) and solution \(S\). This is due because a non-negative linear combination of monotone submodular functions is also monotone and submodular. ```
Input :DAG \(G=(V,E)\), \(B,w_{v},p_{v}\)\(\forall v\in V\) Output :Set \(S\) of edges
1\(S:=\emptyset\)
2\(E^{\prime}:=\{e=(u,s)|u\) is sink and \(s\) is the only source\(\}\) while\(|S|\leq B\)do
3\(e^{\prime}:=\operatorname*{arg\,max}_{e\in E^{\prime}\setminus S}f(S\cup\{e\})\)
4\(S:=S\cup\{e^{\prime}\}\)
```  
**Algorithm 2**Greedy Algorithm for single source. **Theorem 4**. : _Function \(f(S)\) is monotone and submodular with respect to any feasible solution for MCI on DAGs with a single source._  
Proof. : To prove that \(f(S)\) is monotone, we prove that for each \(v\in V\), \(S\subseteq E^{\prime}\), and \(e=(t^{\prime},s)\in E^{\prime}\setminus S\), we have \(p(R(v,S\cup\{e\}))\geq p(R(v,S))\). We first notice that for each node \(v\in V\) and solution \(S\), if there exists an edge \((t,s)\in S\) such that \(t\in R(v)\), then \(p(R(v,S))=p(R(s))\); otherwise, \(p(R(v,S))=p(R(v))\). The same holds for \(p(R(v,S\cup\{e\}))\).