# Adding Edges for Maximizing Weighted Reachability +
## 5 Polynomial-Time Algorithm for DAG with a Single Source or a Single Sink  
In this section, we focus on the case of weighted DAGs in which we have a single source node or a single sink node. We first describe our greedy algorithm to approximate MCI on DAGs with a single source. Then, we show how to modify the algorithm for the case of DAGs with a single sink. In the case of a single source, by using the property of Lemma 2, we restrict our choices to the edges that connect sinks nodes to the source. Let us denote \(S\) as the set of edges added to \(G\). With a little abuse of notation, we also use \(S\) to denote the set of sinks from which the edges in \(S\) start. Note that no information is lost in this way, since we have a DAG with a single source, at most one edge is added for each sink. In fact, if a second edge is added to a sink, this edge would not bring any increase to the objective function. The Greedy algorithm for MCI on DAGs with a single source (see Algorithm 2), starts with an empty solution \(S=\emptyset\) and repeatedly adds to \(S\) the edge \(e^{\prime}\) that maximises the function \(f(S\cup\{e^{\prime}\})\). The edge \(e^{\prime}\) is chosen from the set \(E^{\prime}\) of edges \((u,s)\), where \(u\) is a sink in \(V\), not already inserted in \(S\), and \(s\) is the single source in \(V\) (see Lines 2 and 4). To implement the Greedy Algorithm with a single source, some preprocessing is required. First, for each node \(v\in V\), we perform a DFS visit on \(G\) to compute \(R(v)\) and \(p(R(v))\). We store \(p(R(v,S))\) in a vector \(\rho\) of size \(|V|\). Every time a new edge is added to the solution \(S\), each entry of \(\rho\) is updated in constant time because for each node \(v\), \(p(R(v,S))\) is either equal to \(p(R(v))\) or \(p(R(s))\), as we explain below. To compute the gain of adding the edge \(e=(u,s)\), we need to find all the nodes \(R^{T}(u,S)\) that reach \(u\) in \(G(S)\). \(R^{T}(u,S)\) is computed by performing a DFS visit starting from \(u\) on the reverse graph \(G^{T}(S)\) of \(G(S)\). Note that the reverse graph \(G^{T}\) of \(G\) is initially computed in a preprocessing phase in \(\mathcal{O}(|V|+|E|)\) time, and after every new edge is added to \(S\), \(G^{T}(S)\) is updated in constant time. Finally, to compute \(f(S\cup\{e\})\) for \(e=(u,s)\), observe that \(f(S\cup\{e\})=f(S)+\sum_{z\in R^{T}(u,S)}w_{z}(p(R(s))-p(R(z,S)))\). After selecting the edge \(e^{\prime}=(u,s)\) that maximise \(f(S\cup\{e^{\prime}\})\), we update \(S\) and we set \(p(R(z,S))=p(R(s))\) for each node \(z\in R^{T}(u,S)\) in vector \(\rho\) because \(z\) reaches \(s\) traversing the edge \(e^{\prime}=(u,s)\) and inherits the reachability of \(R(s)\). The Greedy algorithm with a single source requires \(\mathcal{O}(B|V||E|)\) time. Namely, for each edge \(e=(u,s)\in E^{\prime}\), to compute \(f(S\cup\{e\})\) it is required \(\mathcal{O}(|E|)\) time to compute \(R^{T}(u,S)\) on \(G^{T}\), and \(\mathcal{O}(|V|)\) time to compute \(\sum_{z\in R^{T}(u,S)}w_{z}(p(R(s))-p(R(z,S)))\). Since there are \(\mathcal{O}(|V|)\) sinks, the computation of the maximum value at Line 4 costs \(\mathcal{O}(|V||E|)\) time. Selected \(e^{\prime}\), \(\mathcal{O}(|V|)\) time is spent to update \(\rho\). Since at most \(B\) edges are added, the Greedy algorithm requires \(\mathcal{O}(B|V||E|)\). In the following, we describe the algorithm to compute a solution in the case of DAGs with a single sink. The main differences compared to the previous case mainly concern the preprocessing phase of the algorithm. The greedy algorithm remains the same except that we change the set \(E^{\prime}\) from which the edges are chosen in the following way: we substitute \(E^{\prime}\) on Line 2 with the set of edges \((d,v)\), where \(v\) is a source in \(V\) and \(d\) is the only sink in \(V\) (see Line 2) by Lemma 2.