Frequent Itemset-Driven Search for Finding Minimal Node Separators and its Application to Air Transportation Network Analysis

The α-separator problem ( α-SP) consists of finding the minimum set of vertices whose removal separates the network into multiple different connected components with fewer than a limited number of vertices in each component, which belongs to the family of critical node detection problems. The α-SP problem is an important NP-hard problem with various real-world applications. In this paper, we propose a frequent itemset-driven search (FIS) algorithm to solve α-SP, which integrates the concept of frequent itemset into the well-known memetic search framework. Starting from a high-quality population built by population construction and population repair, FIS then iteratively employs a frequent itemset recombination operator (to generate promising offspring solution), a tabu-based simulated annealing (to find local optima), a population repair procedure, and a population management strategy (to guarantee healthy/diverse population). Extensive evaluations on 50 benchmark instances show that FIS significantly outperforms the state-of-the-art algorithms. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds. Finally, we experimentally analyze the importance of each key algorithmic component, and perform a case study on an air transportation network for understanding its network structure and identifying its influential airports.