# Adding Edges for Maximizing Weighted Reachability +
## 2 Preliminaries  
Let \(G=(V,E)\) be a directed graph. Each node \(v\in V\) is associated with a non-negative weight \(w_{v}\in\mathbb{N}_{\geq 0}\) and a profit \(p_{v}\in\mathbb{N}_{\geq 0}\). Given a node \(v\in V\), we denote by \(R(v,G)\) the set of nodes that are reachable from \(v\) in \(G\), that is \(R(v,G)=\{u\in V:\exists\text{ path from }v\text{ to }u\text{ in }\ G\}\). Moreover, we denote by \(p(R(v,G))=\sum_{u\in R(v,G)}p_{u}\) the sum of the profits of the nodes reachable from \(v\) in \(G\). In the rest of the paper, we also use the form \(p(R(v,G)\setminus R(u,G))=\sum_{u\in R(v,G)\setminus R(u,G)}p_{u}\) to denote the sum of the profits of the nodes in \(G\) that are reachable from \(v\), but not from \(u\). Note that, in the case \(R(u,G)\subseteq R(v,G)\), it holds \(p(R(v,G)\setminus R(u,G))=p(R(v,G))-p(R(u,G))\). Given a set \(S\) of edges not in \(E\), we denote by \(G(S)\) the graph augmented by adding the edges in \(S\) to \(G\), i.e., \(G(S)=(V,E\cup S)\). Let \(R(v,G(S))\) and \(p(R(v,G(S)))\) be, respectively, the set of nodes that are reachable from \(v\) in \(G(S)\) and the sum of the profits of the nodes in \(R(v,G(S))\). Note that, augmenting \(G\), the connectivity cannot be worse, and thus: \(R(u,G)\subseteq R(u,G(S))\). Let \(f(G)=\sum_{v\in V}w_{v}p(R(v,G))\) be a weighted measure of the connectivity of \(G\). When weights and profits are unitary, \(f(G)\) represents the overall number of connected pairs in \(G\). In this paper, we aim to augment \(G\) by adding a set \(S\) of edges of at most size \(B\), i.e., \(|S|\leq B\) and \(B\in\mathbb{N}_{\geq 0}\), that maximises the weighted connectivity of \(f(G(S))\). We call this problem the _Maximum Connectivity Improvement_ (MCI) problem because maximising \(f(G(S))\) is the same as maximising \(f(G(S))-f(G)\). Formally,  
**Definition 1** (Maximum Connectivity Improvement). : _Given a graph \(G=(V,E)\), given for each node \(v\in V\) a weight \(w_{v}\in\mathbb{N}_{\geq 0}\) and a profit \(p_{v}\in\mathbb{N}_{\geq 0}\) and given a budget \(B\in\mathbb{N}_{\geq 0}\), we want to find a set of edges \(S^{*}\) such that_  
\[S^{*}=\operatorname*{arg\,max}_{S\subseteq V\times V;|S|\leq B}f(G(S)).\]  
From now on, for simplicity, we omit from the notations the original graph \(G\). Thus, we simply use \(R(v)\) and \(R(v,S)\) to denote \(R(v,G)\) and \(R(v,G(S))\), respectively. Similarly, we simply denote with \(f\) and \(f(S)\) the value of the weighted connectivity in \(G\) and in \(G(S)\), respectively. At first, we show how to transform any directed graph \(G\) with cycles into a _Directed Acyclic Graph_ (DAG) \(G^{\prime}=(V^{\prime},E^{\prime})\) and how to transform any solution for \(G^{\prime}\) into a feasible solution for \(G\). Graph \(G^{\prime}=(V^{\prime},E^{\prime})\) has as many nodes as the number of strongly connected components of \(G\), i.e., there is one vertex in \(V^{\prime}\) for each strongly connected component of \(G\). Specifically, \(G^{\prime}\) selects one representative node for each strongly connected component of \(G\) and \(G^{\prime}\) adds one directed edge between two nodes \(u^{\prime}\) and \(v^{\prime}\) of \(G^{\prime}\) if there is a directed edge in \(G\) connecting any vertex of the strongly connected component represented by \(u^{\prime}\) with any vertex of the strongly connected component represented by \(v^{\prime}\). Graph \(G^{\prime}\) is called _condensation_ of \(G\) and can be computed in \(\mathcal{O}(|V|+|E|)\) time by using [PERSON]'s algorithm which consists in performing a DFS visit [24]. The weight and the profit of a node \(v^{\prime}\) in \(G^{\prime}\) is given by the sum of the weights and profits of the nodes of \(G\) that belong to the strongly connected component \(C_{v^{\prime}}\) that is represented by \(v^{\prime}\), i.e., \(w_{v^{\prime}}=\sum_{v\in C_{v^{\prime}}}w_{v}\) and \(p_{v^{\prime}}=\sum_{v\in C_{v^{\prime}}}p_{v}\).