  The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem in
which given a graph $G$, one aims to find a cut of minimum size such that both
the sides of the cut have at least $cn$ vertices. In this paper, we present new
directions of progress in the {\sc $c$-Balanced Separator} problem. More
specifically, we propose a family of mathematical programs, that depend upon a
parameter $p > 0$, and is an extension of the uniform version of the SDPs
proposed by Goemans and Linial for this problem. In fact for the case, when
$p=1$, if one can solve this program in polynomial time then simply using the
Goemans-Williamson's randomized rounding algorithm for {\sc Max Cut}
\cite{WG95} will give an $O(1)$-factor approximation algorithm for {\sc
$c$-Balanced Separator} improving the best known approximation factor of
$O(\sqrt{\log n})$ due to Arora, Rao and Vazirani \cite{ARV}. This family of
programs is not convex but one can transform them into so called
\emph{\textbf{concave programs}} in which one optimizes a concave function over
a convex feasible set. It is well known that the optima of such programs lie at
one of the extreme points of the feasible set \cite{TTT85}. Our main
contribution is a combinatorial characterization of some extreme points of the
feasible set of the mathematical program, for $p=1$ case, which to the best of
our knowledge is the first of its kind. We further demonstrate how this
characterization can be used to solve the program in a restricted setting.
Non-convex programs have recently been investigated by Bhaskara and
Vijayaraghvan \cite{BV11} in which they design algorithms for approximating
Matrix $p$-norms although their algorithmic techniques are analytical in
nature.
