Critical Node Detection Problem: Benchmark Instances

This page contains benchmark problem instances for the critical node detection problem, as described in the papers:

M. Ventresca, Global Search Algorithms Using a Combinatorial Unranking-Based Problem Representation for the Critical Node Detection Problem, Computers and Operations Research, 39(11):2763-2775, 2012.

M. Ventresca, K. Harrison and B. Ombuki-Berman, The Bi-Objective Critical Node Detection Problem, European Journal of Operational Research, 254(3):895-908, 2018.

There are four classes of problems, each generated from different parameterizations of popular complex network topologies. Parameterization is discussed in the aforementioned paper. The file format is as follows: line 1 contains the number of vertices. The remaining lines contain the vertex number, followed by a colon, and a list of connected vertices. That is, this representation is an adjacency list of the undirected graph. The second set represents weighted versions of the same networks. Download all unweighted networks here and weighted networks here.