On the Maximum Connectivity Improvement Problem

In this paper, we define a new problem called the Maximum Connectivity Improvement (MCI) problem: given a directed graph a weight function (formula presented), a profit function (formula presented), and an integer B, find a set S of at most B edges not in E that maximises (formula presented), where p(R(v, S)) is the sum of the profits of the nodes reachable from node v when the edges in S are added to G. We first show that we can focus on Directed Acyclic Graphs (DAG) without loss of generality. We prove that the MCI problem on DAG is NP-Hard to approximate to within a factor greater than 1-1/e even if we restrict to graphs with a single source or a single sink, and MCI remains NP -Complete if we further restrict to unitary weights. We devise a polynomial time algorithm based on dynamic programming to solve the MCI problem on trees with a single source. We propose a polynomial time greedy algorithm that guarantees (1-1/e) -approximation ratio on DAGs with a single source or a single sink.