Computing Critical Nodes in Directed Graphs
Nilakantha Paudel, Loukas Georgiadis, Giuseppe Francesco Italiano · ACM Journal of Experimental Algorithmics · 2018
We consider the critical node detection problem (CNDP) in directed graphs, which can be defined as follows. Given a directed graph G and a parameter k , we wish to remove a subset S of at most k vertices of G 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.