Critical Node Detection Problem: Benchmark Instances

This page contains benchmark problem instances for the critical node detection problem, as described in the paper: M. Ventresca, Global Search Algorithms Using a Combinatorial Unranking-Based Problem Representation for the Critical Node Detection Problem, Computers and Operations Research, 2012.

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. Download all graphs here