# Adding Edges for Maximizing Weighted Reachability +
## 1 Introduction  
The problem of improving the reachability of a graph is an important graph-theoretical question, which finds applications in several areas. There are several recent possible application scenarios for this problem, for example suggesting friends in a social network in order to increase the spreading of information [1; 2; 3], reducing the convergence time of random walk processes to perform faster network simulations [4; 5], improving wireless sensor networks resilience [6] and even control elections in social networks [7; 8]. In this paper, we approach the problem from a graph augmentation perspective, which is the problem of adding a set of non-existing edges to a graph to increase the overall number of reachable nodes. In traditional graph theory, this problem was first studied by [PERSON] and [PERSON] [9]. They considered the problem of adding a minimum-cost set of edges to a graph such that the resulting graph satisfies a given connectivity requirement, e.g., to make a directed graph strongly connected or to make an undirected graph bridge-connected or biconnected. In their seminal paper, [PERSON] et al. presented linear time algorithms for many graph augmentation problems and proved that some variants are instead _NP_-complete. More recently, several optimisation problems related to graph augmentation have been addressed. Several papers in the literature deal with the problem of minimising the eccentricity of a graph by adding a limited number of new edges [10; 11; 12; 13]. The problem of minimising the average all-pairs shortest path distance--characteristic path length--of the whole graph was studied by [PERSON] [5]. The author considered the problem of adding a small set of edges to minimise the characteristic path length and proves that the problem is _NP_-hard. He proposed a path screening technique to select the edges to be added. It is worth noting that the objective function in [5] does not satisfy the submodularity property, and so good approximations cannot be guaranteed via a greedy strategy. The problem of adding a small set of links to maximise the centrality of a given node in a network has been addressed for different centrality measures: page-rank [4; 14], average distance [15], harmonic and betweenness centrality [16; 17] and some measures related to the number of paths passing through a given node [18]. It is worth noting that many traditional graph problem can also be applied to dynamic graphs. Graph problems close to ours studied in the dynamic setting include connectivity [19], minimum spanning tree [20] and reachability [21; 22]. In this work, which is based on and extends previous preliminary research in this direction [23], we study the problem of adding at most \(B\) edges to a directed graph in order to maximise the overall weighted number of reachable nodes, which we call the _Maximum Connectivity Improvement_ (MCI) problem. The rest of the paper is organised as follows. We first show that we can focus on Directed Acyclic Graphs (DAG) without loss of generality (Section 2). Then, we focus on the complexity of the problem (Section 3) and we prove that the MCI problem is _NP_-hard to approximate to within a factor greater than \(1-\frac{1}{e}\). This result holds even if the DAG has a single source or a single sink. Moreover, the problem remains _NP_-complete if we further restrict to the unweighted case. In Section 4, we give a dynamic programming algorithm for the case in which the graph is a rooted tree, where the root is the only source node. In Section 5, we present a greedy algorithm which guarantees a \((1-1/e)\)-approximation factor for the case in which the DAG has a single source or a single sink. As a first step in the direction of extending our approach to general DAGs, i.e., multiple sources and multiple sinks, in Section 6, we tackle the special case of DAGs with two sources providing a constant factor approximation algorithm to solve the problem. We end with some concluding remarks in Section 7.