On Single Source Reachability Improvement

Abstract

The problem of augmenting a given network, or graph, via edge-additions for improved reachability from a given source node is considered. We formulate and study the following Single Source Reachability Improvement problem (SSRI): given a graph G = (II, E), with a special (source) vertex s and two nonnegative integers d and k, can the addition of at most k edges result in a graph in which every vertex is at distance at most d from the source vertex. We also study the partial variant of the problem, which requires that at least some percentage of the vertices be within a distance of d from the source vertex. To the best of our knowledge, this partial variant has not been studied previously. We investigate the computational complexity of our problem with respect to the number of edge additions and the desired distance-bound. We show the NP­ hardness and present an effective polynomial-time greedy algorithm. Experimental evaluation of our greedy algorithm is conducted on randomly generated graphs, using the Erdos-Renyi approach. Compared to previously known methods, our ap­proach exhibits constant increase in the effectiveness by using smaller number of edge addition operations to achieve total reachability. Finally, we study a new vari­ant of the problem, dubbed Bounded Capacity Reachability Improvement (BCRI). In this case, each vertex can have a given limited number of edges connected to it. Experimental results show that our greedy method, applied to BCRI instances, is highly effective on weekly connected graphs.