In the Maximum Connectivity Improvement (MCI) problem, we are given a directed graph G = (V,E) and an integer B and we are asked to find B new edges to be added to G in order to maximize the number of connected pairs of vertices in the resulting graph. The MCI problem has been studied from the approximation point of view. In this paper, we approach it from the parameterized complexity perspective in the case of directed acyclic graphs. We show several hardness and algorithmic results with respect to different natural parameters. Our main result is that the problem is W[2]-hard for parameter B and it is FPT for parameters |V |- B and nu, the matching number of G. We further characterize the MCI problem with respect to other complementary parameters.
On the Fixed-Parameter Tractability of the Maximum Connectivity Improvement Problem
Corò F.;
2020
Abstract
In the Maximum Connectivity Improvement (MCI) problem, we are given a directed graph G = (V,E) and an integer B and we are asked to find B new edges to be added to G in order to maximize the number of connected pairs of vertices in the resulting graph. The MCI problem has been studied from the approximation point of view. In this paper, we approach it from the parameterized complexity perspective in the case of directed acyclic graphs. We show several hardness and algorithmic results with respect to different natural parameters. Our main result is that the problem is W[2]-hard for parameter B and it is FPT for parameters |V |- B and nu, the matching number of G. We further characterize the MCI problem with respect to other complementary parameters.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
