In this paper, we define a new problem called the Maximum Connectivity Improvement (MCI) problem: given a directed graph =(,), a weight function :→ℕ≥0, a profit function :→ℕ≥0, and an integer B, find a set S of at most B edges not in E that maximises ()=∑∈⋅((,)), 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 -Hard to approximate to within a factor greater than 1−1/ even if we restrict to graphs with a single source or a single sink, and MCI remains -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/)-approximation ratio on DAGs with a single source or a single sink.
On the Maximum Connectivity Improvement Problem
CORO', FEDERICO
;D’Angelo, Gianlorenzo;Pinotti, Cristina M.
2019
Abstract
In this paper, we define a new problem called the Maximum Connectivity Improvement (MCI) problem: given a directed graph =(,), a weight function :→ℕ≥0, a profit function :→ℕ≥0, and an integer B, find a set S of at most B edges not in E that maximises ()=∑∈⋅((,)), 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 -Hard to approximate to within a factor greater than 1−1/ even if we restrict to graphs with a single source or a single sink, and MCI remains -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/)-approximation ratio on DAGs with a single source or a single sink.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
