  Finding an optimal set of critical nodes in a complex network has been a
long-standing problem in the fields of both artificial intelligence and
operations research. Potential applications include epidemic control, network
security, carbon emission monitoring, emergence response, drug design, and
vulnerability assessment. In this work, we consider the problem of finding a
minimal node separator whose removal separates a graph into multiple different
connected components with fewer than a limited number of vertices in each
component. To solve it, we propose a frequent itemset-driven search approach,
which integrates the concept of frequent itemset mining in data mining into the
well-known memetic search framework. Starting from a high-quality population
built by the solution construction and population repair procedures, it
iteratively employs the frequent itemset recombination operator (to generate
promising offspring solution based on itemsets that frequently occur in
high-quality solutions), tabu search-based simulated annealing (to find
high-quality local optima), population repair procedure (to modify the
population), and rank-based population management strategy (to guarantee a
healthy population). Extensive evaluations on 50 widely used benchmark
instances show that it significantly outperforms state-of-the-art algorithms.
In particular, it discovers 29 new upper bounds and matches 18 previous
best-known bounds. Finally, experimental analyses are performed to confirm the
effectiveness of key algorithmic modules of the proposed method.
