Two New Exact Methods for the Vertex Separation Problem

Abstract

The Vertex Separation Problem (VSP) is an NP-hard combinatorial optimization problem in the context of graph theory. Particularly, VSP belongs to a family of linear ordering problems in which the goal is to find the best separator of vertices in a generic graph. In the literature reviewed, we only found two exact methods based on integer linear programming (IP) formulations. The main contribution of this paper is that we have extended the available exact methods by proposing an ad hoc branch and bound algorithm (BBVSP) and a new IP formulation (IPVSP). The experimental results show that BBVSP is the best method since it found the largest number of optimal solutions and achieved the lowest computing time. More precisely, BBVSP found 100 optimal values out of 108 instances evaluated, which represents an effectiveness of 92.6%. BBVSP also achieves a saving of time of about 91.1% with respect to the best exact IP formulation found in the literature.