An Ant Colony Optimization approach to solving the Vertex Separator Problem

This article presents an Ant Colony Optimization (ACO) algorithm, enhanced with problem-specific heuristics, for solving the Vertex Separator Problem (VSP). The VSP aims to find three disjoint subsets A, B, and C from the vertex set V of a graph G = (V, E), such that C forms a separator between A and B while minimizing |C| under cardinality constraints on A and B. The proposed method uses a colony of ants that construct solutions by assigning vertices probabilistically based on pheromone trails and problem-specific heuristics. A local search is introduced to refine these solutions, while adaptive pheromone updates and simulated annealing components are added to help escape local minima. Current studies concentrate on integer linear programming or heuristic approaches. This article details a novel metaheuristic solution, based on multiple heuristic functions, which are key to guiding the search process. We compare our solution to a greedy algorithm and heuristics from previous studies. The initial results proved encouraging, with ACO achieving better results compared to state-of-the-art heuristics on 15 of the 62 benchmarked problem instances.