@techreport{TR-IC-04-09,
number = {IC-04-09},
author = {E. Balas and C. C. de Souza},
title = {The Vertex Separator Problem: A Polyhedral Investigation},
month = {August},
year = {2004},
institution = {Institute of Computing, University of Campinas},
note = {In English, 35 pages.
\par\selectlanguage{english}\textbf{Abstract}
The vertex separator (VS) problem in a graph $G=(V,E)$ asks for
a partition of $V$ into nonempty subsets $A$, $B$, $C$ such
that there is no edge between $A$ and $B$, and $|C|$ is
minimized subject to a bound on $\max\{|A|,|B|\}$. We give a
mixed integer programming formulation of the problem and
investigate the vertex separator polytope (VSP), the convex
hull of incidence vectors of vertex separators. Necessary and
sufficient conditions are given for the VSP to be full
dimensional. Central to our investigation is the relationship
between separators and dominators. Several classes of valid
inequalities are investigated, along with the conditions under
which they are facet defining for the VSP. Some of our proofs
combine in new ways projection with lifting.
\par
In a companion paper we develop a branch-and-cut algorithm for
the (VS) problem based on the inequalities discussed here, and
report on computational experience with a wide variety of (VS)
problems drawn from the literature and inspired by various
applications.
}
}