  The Vertex Separator Problem for a graph is to find the smallest collection
of vertices whose removal breaks the graph into two disconnected subsets that
satisfy specified size constraints. In the paper 10.1016/j.ejor.2014.05.042,
the Vertex Separator Problem was formulated as a continuous
(non-concave/non-convex) bilinear quadratic program. In this paper, we develop
a more general continuous bilinear program which incorporates vertex weights,
and which applies to the coarse graphs that are generated in a multilevel
compression of the original Vertex Separator Problem. A Mountain Climbing
Algorithm is used to find a stationary point of the continuous bilinear
quadratic program, while second-order optimality conditions and perturbation
techniques are used to escape from either a stationary point or a local
maximizer. The algorithms for solving the continuous bilinear program are
employed during the solution and refinement phases in a multilevel scheme.
Computational results and comparisons demonstrate the advantage of the proposed
algorithm.
