A branch-and-price based heuristic for the Vertex Separator Problem

For a given graph, a vertex separator is a subset of the vertex set of a graph whose removal disconnects the graph. If the graph has n vertices and b(n) is a positive integer number, then the Vertex Separator Problem (VSP) asks to find a minimum cardinality vertex separator such that the remaining vertices can be partitioned in two edge-disconnected classes of cardinality at most b(n).We introduce a new integer linear programming (ILP) model for VSP which is based on a very large number of variables and present an heuristic based on the corresponding branch-and-price algorithm. One of the advantages of our formulation is the simplicity of the resulting subproblems. The numerical experiments proved to be very encouraging: even after truncating our algorithm to one hour run, from 62 tested instances we got better results for 10 instances and for another 33 instances we get even with the state-of-the-art approaches.