Computing critical nodes in directed graphs

We consider the critical node detection problem (CNDP) in directed graphs, which can be defined as follows. Given a directed graphG and a parameter k, we wish to remove a subset S of at most k vertices ofG such that the residual graph G\S has minimum pairwise strong connectivity. This problem is NP-hard, and thus we are interested in practical heuristics. In this article, we apply the framework of Georgiadis et al. (SODA 2017) and provide a sophisticated linear-time algorithm for the k = 1 case. Based on this algorithm, we provide an efficient heuristic for the general case. Then, we conduct a thorough experimental evaluation of various heuristics for CNDP. Our experimental results suggest that our heuristic performs very well in practice, both in terms of running time and of solution quality.