# Adding Edges for Maximizing Weighted Reachability +
## 6 Polynomial-Time Algorithm for DAG with Two Sources  
In this section, we take a first step in the direction of studying the MCI problem in general DAGs, i.e., multiple sources and multiple sinks, by tackling the special case of weighted DAGs with two source nodes. In the following, we describe an approach that can be easily extended to the case of DAGs with a constant number of sources. However, this approach can be computationally heavy as the number of such sources increases. We first prove an important property that we exploit to provide a polynomial-time algorithm for this case. The idea is that, if we add an initial edge to the solution, then any other added edge is toward the opposite source node. Using this property, we are able to reduce the number of possible solutions that we have to consider. Furthermore, this allows us to use the greedy algorithm that we proposed in the previous section to solve the problem. In this section, we improve the notation by defining \(s_{1},s_{2}\) the two sources and by \(L_{1},L_{2}\) the sink nodes reachable from source \(s_{1}\) and \(s_{2}\), respectively. Note that we allow \(L_{1}\cap L_{2}\
eq\emptyset\), i.e., the two sources may share sink nodes. Lemma 3: _Let \(S\) be a solution to the MCI problem in a graph \(G=(V,E)\) with two sources \(s_{1},s_{2}\); then, there exists a solution \(S^{\prime}\) such that \(|S^{\prime}|=|S|\) with \(f(S^{\prime})\geq f(S)\), and \(S^{\prime}\) contains at most one edge \(e\) directed towards source \(s_{1}\) (\(s_{2}\), respectively), while all the other edges are directed towards \(s_{2}\) (\(s_{1}\), respectively)._  
Proof: Let us first consider the following case: there exists in \(S\) at least one edge connecting a sink in \(L_{2}\) with the source \(s_{1}\), i.e., edge \((v_{i},s_{1})\in S\) with \(v_{i}\in L_{2}\). Note that this case is equivalent to connecting a node in \(L_{1}\) to \(s_{2}\). Now, for any other edge \(e_{1}=(v_{j},s_{1})\in S\), we prove that we can change such edge to connect to source \(s_{2}\), i.e., \(e_{2}=(v_{j},s_{2})\), without decreasing the objective function. In fact, note that, for any node \(z\in R^{T}(v_{j},S)\) and solution \(S\), we have that \(p(R(z,S))\) can be either equal to \(p(R(V))\), if there exists a path that connect such node to source \(s_{2}\), or equal to \(R(s_{1})\) by using edge \(e_{1}\). Instead, by using edge \(e_{2}\), we have that any node \(z\in R^{T}(v_{j},S)\) is able to reach any node in the graph, thus having profit \(p(R(V))\). Therefore, we have that \(f(S)\leq f((S\cup e_{2})\setminus e_{1})\) since any node that is able to reach sink \(v_{j}\) in solution \((S\cup e_{2})\setminus e_{1}\) actually reaches all the nodes in the graph. On the other hand, it must be that all edges in \(S\) are of the kind \((v_{i},s_{1})\) with \(v_{i}\in L_{1}\) or \((v_{i},s_{2})\) with \(v_{i}\in L_{2}\), i.e., all the edges from \(L_{1}\) are toward source \(s_{1}\) (\(s_{2}\), respectively). Let us divide solution \(S\) in two subsets: \(S_{1}\) containing all the edges of kind \((v_{i},s_{1})\) with \(v_{i}\in L_{1}\), and \(S_{2}\), respectively, with edges of kind \((v_{i},s_{2})\) with \(v_{i}\in L_{2}\). Then, by changing one edge from \(S_{1}\) in \((v_{j},s_{2})\) and all the edges in \(S_{2}\) toward \(s_{1}\) we have increased the objective function, since now all the nodes in a path to one of the sources are able to reach any node in the graph. The lemma above shows us that we can build a solution for the MCI problem by selecting one initial edge and then we can use the greedy algorithm to choose the rest of the edges. In fact, after we have added the initial edge, we can exploit the algorithm given in Section 5, since the DAG now has only one source node and thus the submodularity holds. The underlying idea for the algorithm is to create \(2\cdot|L_{1}\cup L_{2}|\) different instances by enumerating all possible combination of one initial edge, then, we run the greedy algorithm in each of this instances and we choose the best solution among them.