# Adding Edges for Maximizing Weighted Reachability +
## 2 Preliminaries
Note that, when the profits are unitary in \(G\), \(p_{v}=1\)\(\forall v\in V\), then \(p_{v^{\prime}}\) is equal to the size of the strongly connected component \(C_{v^{\prime}}\) associated to \(v^{\prime}\). Since the condensation preserves the connectivity of \(G\), the following lemma can be proved:  
**Lemma 1**. : _Given a graph \(G\) and its condensation \(G^{\prime}\), it yields: \(f(G^{\prime})=f(G)\)._  
Proof. : First, consider two nodes \(u\) and \(v\) that belong to the same strongly connected component \(C_{v^{\prime}}\) in \(G^{\prime}\). Clearly, \(R(u,G)=R(v,G)\). Moreover, it holds that \(p(R(v,G))=p(R(v^{\prime},G^{\prime}))\) because \(R(v^{\prime},G^{\prime})\) contains one node for each different strongly connected component in \(R(u,G)\) and thus:  
\[p(R(v^{\prime},G^{\prime}))=\sum_{u^{\prime}\in R(v^{\prime},G^{\prime})}p_{u^ {\prime}}=\sum_{u^{\prime}\in R(v^{\prime},G^{\prime})}\sum_{u\in C_{u^{ \prime}}}p(u)=\sum_{u\in R(v,G)}p(u)=p(R(v,G))\]  
Denoting \(C_{v^{\prime}}\) the strongly connected component represented by \(v^{\prime}\), we have:  
\[f(G^{\prime}) =\sum_{\mathbf{v}^{\prime}\in V^{\prime}}w_{\mathbf{v}^{\prime}} p(R(\mathbf{v}^{\prime},G^{\prime}))\] \[=\sum_{\mathbf{v}^{\prime}\in V^{\prime}}w_{\mathbf{v}^{\prime}} \left(\sum_{u^{\prime}\in R(\mathbf{v}^{\prime},G^{\prime})}\sum_{u\in C_{u^{ \prime}}}p(u)\right)=\sum_{\mathbf{v}^{\prime}:C_{v^{\prime}}\in C}w_{\mathbf{v} ^{\prime}}\left(\sum_{u^{\prime}\in R(\mathbf{v}^{\prime},G^{\prime})}\sum_{ u\in C_{u^{\prime}}}p(u)\right)\] \[=\sum_{\mathbf{v}^{\prime}:C_{v^{\prime}}\in C}\left(\sum_{v\in C _{v^{\prime}}}w_{v}\sum_{u\in R(v,G)}p(u)\right)=\sum_{\mathbf{v}^{\prime}:C_{ v^{\prime}}\in C}\sum_{v\in C_{v^{\prime}}}w_{v}p(R(v,G))\] \[=\sum_{\mathbf{v}\in V}w_{v}p(R(v,G))=f(G)\]Given a solution \(S^{\prime}\) for the MCI problem in \(G^{\prime}\), we can build a solution \(S\) with the same value for the MCI problem in \(G\) as follows: For each edge \((u^{\prime},v^{\prime})\) in \(S^{\prime}\), we add an edge \((u,v)\) in \(S\), where \(u\) and \(v\) are two arbitrary nodes in the connected component corresponding to \(u^{\prime}\) and \(v^{\prime}\), respectively. This derives from the fact that applying the condensation algorithm to \(G^{\prime}\cup S^{\prime}\) or to \(G\cup S\) we obtain the same condensed graph, say \(G^{\prime\prime}\). From Lemma 1, we can conclude that \(f(G^{\prime}\cup S^{\prime})=f(G^{\prime\prime})=f(G\cup S)\). Observe that, if we add an edge \(e\) within the same strongly connected component in \(G\), we do not add any edge to \(G^{\prime}\). Since the condensation \(G^{\prime\prime}\) of \((G\cup\{e\})\) is the same as \(G^{\prime}\), we have \(f(G\cup\{e\})=f(G^{\prime})=f(G)\). Hence, we can assume, without loss of generality, that any solution to MCI in \(G\) does not contain any edge within a unique strongly connected component since such edge does not improve the objective function. As a consequence, in the remainder of the paper, we assume that the graph is a DAG. Given a DAG, we can distinguish between three kinds of nodes: _sources_, nodes with no incoming edges; _sinks_, nodes with no outgoing edges; and the rest of the nodes. The next lemma allows us to focus on solutions that contain only edges connecting sink nodes to source nodes. In the remainder of the paper, we use this property to derive algorithms to solve both the simple case with binary trees and the more general case with DAGs (with single or double source and single sink). Lemma 2: _Let \(S\) be a solution to the MCI problem, then there exists a solution \(S^{\prime}\) such that \(|S|=|S^{\prime}|\), \(f(S)\leq f(S^{\prime})\), and all edges in \(S^{\prime}\) connect sink nodes to source nodes._  
Proof: We show how to modify any solution \(S\) in order to find a solution \(S^{\prime}\) that contains only nodes that connect sink nodes to source nodes with the same cardinality and such that \(f(S)\leq f(S^{\prime})\).