On the fixed-parameter tractability of the maximum connectivity improvement problem

Federico Corò, Gianlorenzo D'Angelo, Vahan Mkrtchyan

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…