@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.
  }
}