\documentstyle[epsf,epic,eepic,12pt]{article}
\newcommand{\doublespace}{\baselineskip=24pt}
\newcommand{\eot}{\mbox{$\rule{2mm}{3mm}$}}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\begin{document}
\title{A Study of Graph Bisection by Positive Semidefinite Programming}
\author{Bo Yu\\
           Department of Combinatorics and Optimization \\
           University of Waterloo, Waterloo, Ontario\\
           Canada, N2L 3G1}
\date{ }
\maketitle
\doublespace
\begin{abstract}
The graph  bisection problem is to partition the vertex set of a graph into
two equal-size pieces $S$ and $\bar{S}$ so that the total weight of edges
with exact one end in $S$
is minimum. We present a positive semidefinite programming formulation for the
problem and some computational testing results of the formulation.
\end{abstract}
\section{Introduction}
Given an edge-weighted  undirected graph with an even number of vertices,
{\em the graph
bisection problem} is to partition the vertex set of the graph into
two equal-size pieces $S$ and $\bar{S}$ so that the total weight of edges
with exact one end in $S$
is minimum. The set of edges between the two 
equal-size pieces $S$ and $\bar{S}$ is called a {\em bisector}.

The graph bisection problem has many applications in  VLSI design~\cite{bl}, 
sparse matrix computations and solving various graph problems.
Unfortunately, the problem is NP-hard ~\cite{gjs}, and people
turn to developing heuristic methods, or considering special
 classes of graphs in which the problem can be solved.

This project firstly formulate a positive semidefinite programming (SDP) relaxation
for the graph bisection problem. Hence the optimal value of the SDP gives us
an lower bound for the problem. Secondly we do some computational testing
 on a few randomly generated
examples. We use the eigenvector corresponding to the maximum eigenvalue of
the optimal solution of the SDP to get a feasible bisector, which serves as
an upperbound for the minimum bisector. The gap, defined by
the difference between the lowerbound and the upperbound divided by the
lowerbound,  lies between zero and twelve percentage in our examples.
We  use a matlab program, written by Rendl and Wolkowicz using the 
interior point method developed by Helmberg et al \cite{hrvw}, to 
do the computation.

\section{SDP Formulation}
In this section we formulate a positive semidefinite programming for the
graph bisection problem using
 Lagrangian multiplier.

 Given an undirected graph $G = (V, E)$ with $V = \{1, \ldots, n\}$,
$n$ is an even number, 
and non-negative weights $w_{ij} = w_{ji}$ on the 
edges $(i,j) \in E$, the weight  of  a bisector $(S,\bar{S})$ is denoted
by $w(S,\bar{S}) = \sum_{i\in S, j \not \in S}w_{ij}$.

We first formulate an integer programming for our problem. 
Let $y_{i} = 1$ for $i \in S$ and $y_{i} = -1$ for $i \in \bar{S}$.
So $w(S,\bar{S}) =$
$\frac{1}{2} \sum_{i<j}w_{ij}(1 - y_{i}y_{j})$
$= \frac{1}{4} \sum_{i,j}w_{ij}(1 - y_{i}y_{j})$, where  
$w_{ii} = 0$. 
Therefore the weight of the minimum bisector
is given by the following integer quadratic program:
\[(IP1) \left \{ \begin{array}{l}
\mbox{Minmize} ~\frac{1}{4} \sum_{i,j}w_{ij}(1 - y_{i}y_{j}) \\
\mbox{subject to} \\
                    ~\sum_{i}y_{i}  = 0\\
                    y_{i} \in \{-1, 1\}, ~\mbox{for all} ~i \in V. \\
\end{array}
     \right. \]
Equivalently, we have the following integer quadratic program:
\[(IP2) \left \{ \begin{array}{l}
\mbox{Minimize} ~\frac{1}{4} (\sum_{i,j}w_{ij}) - ~\frac{1}{4}(y^{t}Wy) \\
\mbox{subject to} \\
                    (~\sum_{i}y_{i})^{2}  = 0\\
                    y_{i}^{2} =  1, ~\mbox{for all} ~i \in V, \\
\end{array}
     \right. \] 
where $y = (y_{1}, y_{2}, \ldots, y_{n})^{t}$ and 
$W$ is the $n\times n$ matrix with $w_{ij}$ as its $(i,j)$ entry.

Now in order to solve $(IP2)$, we only need to consider solving the 
following program:\\
\[(IP3) \left \{ \begin{array}{l}
\mu^{\ast} = \mbox{Maximize}~ y^{t}Wy \\
\mbox{subject to} \\
                    (~\sum_{i}y_{i})^{2}  = 0\\
                    y_{i}^{2} =  1, ~\mbox{for all} ~i \in V. \\
\end{array}
     \right. \]

Since solving an integer quadratic program  is NP-complete in
 general, we consider its relaxation.
Before giving an equivalent formulation for $(IP3)$, we introduce
some standard notations. Let $A = (a_{ij})_{n \times n}$ be a matrix of
size $n \times n$ and $u = (u_{1},
u_{2},\ldots, u_{n})^{t}$ be a column vector. Diag($u)$ denotes  the
diagonal matrix of size $n \times n$ with diagonal 
elements $u_{1},u_{2},\ldots, u_{n}$ and diag($A$) = ($a_{11}, a_{22}, \ldots, a_{nn})^{t}$.
 $J$ is the square matrix with all elements ones.
$e$ is the column vector with all ones. $I_{n}$ is the identity
matrix of size $n$.

Let $\mu^{\ast}$ be the optimal value of ($IP3)$.
Then equivalently, using Lagrangian multipliers, we have
\[\mu^{\ast} = \mbox{max}_{y}\mbox{min}_{\alpha, \beta} L(y, \alpha, \beta) =
\mbox{max}_{y}\mbox{min}_{\alpha, \beta} \{y^{t}Wy - \sum_{i=1}^{n}\alpha_{i}(y_{i}^{2} - 1)
- \beta(\sum_{i}y_{i})^{2}\}\]
\[= \mbox{min}_{\alpha, \beta} \mbox{max}_{y} \{y^{t}Wy - \sum_{i=1}^{n}\alpha_{i}(y_{i}^{2} - 1)- \beta(\sum_{i}y_{i})^{2}\},
 \mbox{~~~~~~~~(by strong duality)}\]
\[= \mbox{min}_{\alpha, \beta} \mbox{max}_{y} \{ \sum_{i=1}^{n}\alpha_{i} +
y^{t} (W - \mbox{Diag}(\alpha) - \beta J) y \}.
~~~~~~~~~~~~~~~~~~~~~~~\]

Therefore $\mu^{\ast}$ is equal to the optimal value of the following
positive semidefinite programming using the hidden constraint of 
above expression.

\[(DIP3) \left \{ \begin{array}{l}
\mu^{\ast} = \mbox{~Minimize} \sum_{i=1}^{n}\alpha_{i} \\
\mbox{subject to} \\
                    \mbox{Diag}(\alpha) + \beta J \succeq W, \\
\end{array}
     \right. \]
where $\alpha = (\alpha_{1}, \alpha_{2}, \ldots, \alpha_{n})^{t}$.

Dual of ($DIP3)$ is
\[(P4) \left \{ \begin{array}{l}
\mu^{\ast} = \mbox{~Maximize}~ tr(WX) \\
\mbox{subject to} \\
                    \mbox{diag}(X) = e \\
tr(XJ) = 0 ~~~~~~~~~~~~~~~~~~~(\ast)\\
X \succeq 0. \\
\end{array}
     \right. \]

If the rank of $X$ in $(P4)$ is one, then $X = yy^{t}$ for some non-zero
 vector $y$ since $X$ is positive semidefinite.
Furthermore if $X$ is substituted by $yy^{t}$ in $(P4)$, we'll get $(IP3)$.
This
indicates that $(P4)$ is indeed a  positive semidefinite
programming relaxation of our problem.
\section{Computational study}
In this section we run a matlab program, designed by Rendl and 
Wolkowicz using the interior point method developed 
by Helmberg et al \cite{hrvw}, to several randomly generated
 examples to find the 
optimal solution of $(P4)$. Moreover we convert the optimal solution
into a bisector, which gives us an upperbound of the minimum bisector.
In the end, we compare the upperbound and the lowerbound given by
the optimal value of $(P4)$. Namely, we consider the gap, defined by
the difference between the lowerbound and the upperbound divided by
the lowerbound. The gap is between zero and twelve percentage in our examples.
Most of the examples has zero gap.

Due to the constraint ($\ast)$ in ($P4)$, the rank of $X$ must
 be less than $n$.
Therefore ($P4)$ has  no interior point. 
In order to use the interior point method to solve $(P4)$, we have to
consider the feasible region of $(P4)$ in a lower dimensional space.

We look at the $(n-1$)-dimensional
vector space which is orthogonal to $e$.
 It is easy to check that the following
$n-1$ vectors form a basis of the $(n-1$)-dimensional space.
 
$v_{1} = (- \frac{1}{\sqrt n}, 1-\frac{1}{n+\sqrt n}, -\frac{1}{n+\sqrt n},
\ldots, -\frac{1}{n+\sqrt n})^{t}$,

$v_{2} = (- \frac{1}{\sqrt n}, -\frac{1}{n+\sqrt n}, 1-\frac{1}{n+\sqrt n},
-\frac{1}{n+\sqrt n}, \ldots, -\frac{1}{n+\sqrt n})^{t},\ldots \ldots,$

$v_{n-1} = (- \frac{1}{\sqrt n}, -\frac{1}{n+\sqrt n}, \ldots,
 -\frac{1}{n+\sqrt n}, 1-\frac{1}{n+\sqrt n})^{t}$.\\
Also $v_{i}$'s are mutually orthogonal and let
 $V = (v_{1}, v_{2}, \ldots, v_{n-1})$.

Furthermore, any such matrix $X$ in $(P4)$ can be written as $VYV^{t}$ where $Y$ is a
positive semidefinite matrix of size $n-1$. (Since $X = U Diag(\lambda_{1},
\lambda_{2}, \ldots, \lambda_{n-1}, 0) U^{t}$ where $U$ is formed by eigenvectors
of $X$ which are mutually orthogonal. $= (U_{1}, e) Diag(\lambda_{1},\lambda_{2}, \ldots, \lambda_{n-1}, 0) (U_{1}, e)^{t} = U_{1} Diag(\lambda_{1},\lambda_{2},
\ldots, \lambda_{n-1}) U_{1}^{t}.$ Since $U_{1}$ can be written as $VB$ for
some matrix $B$ since columns of $U_{1}$ are orthogonal to $e$,
$X = V B Diag(\lambda_{1},\lambda_{2},\ldots, \lambda_{n-1}) B^{t} V^{t}$ and
$Y = B Diag(\lambda_{1},\lambda_{2},\ldots, \lambda_{n-1}) B^{t}$.)

 Therefore $(P4)$ can be rewritten
as follows:
\[(P5) \left \{ \begin{array}{l}
\mbox{Maximize}~ tr(WVYV^{t}) \\
\mbox{subject to} \\
                    \mbox{diag}(VYV^{t}) = e \\
Y \succeq 0 \\
\end{array}
     \right. \]
 
The dual of $(P5)$ is

\[(DP5) \left \{ \begin{array}{l}
\mbox{Minimize}~ u^{t}e \\
\mbox{subject to} \\
                  V^{t}  (\mbox{Diag}(u) - W) V \succeq 0. \\
\end{array}
     \right. \]

Now we can use the interior point method developed by Helmberg et al 
\cite{hrvw}to solve $(P5)$. The initial interior point
for (P5) is $Y = \frac{n^{2}+2n\sqrt{n}}{n^{2}+2n\sqrt{n}-n-2\sqrt{n}} I_{n-1}$. 
The initial interior point for (DP5) can be $u = N e$ for  a sufficient
large integer $N$. Here we  pick $N = n$.


The following is our algorithm:\\
{\bf  Algorithm:}\\
Given an edge weighted graph $G$, compute a lowerbound and an upperbound
of the minimum bisector.

(1) Solve $(P5)$ using interior point method and get an optimal solution
$Y$ and the optimal value $\mu^{\ast}$. The lowerbound is given by
$\frac{1}{4} \sum_{i,j}w_{ij} - \frac{1}{4} \mu^{\ast}$ from $(IP2)$.

(2) Let $X = VYV^{t}$. Solve for the eigenvector $v$ corresponding to the
maximum eigenvalue of $X$.
Find the bisector $(S, \bar{S})$ by choosing the indices,  corresponding
to the $n/2$ largest components of $v$, as $S$. The weight of $(S, \bar{S})$
gives an upperbound.

(4) Compute the gap = $\frac{\mbox{upperbound - lowerbound}}{\mbox{lowerbound}}$. 
\\

{\bf Acknowledgement} The author would like to thank Dr. Wolkowicz and
Qing Zhao for lots of helpful discussions.





\begin{thebibliography}{99}
\bibitem{bl} S. Bhatt and T. Leighton,
A framework for solving VLSI graph problems,
{\em Journal of Computer and System Sciences} 28:2 (1984) 300-343.

\bibitem{frw} J. Falkner, F. Rendl and H. Wolkowicz,
A computational study of graph partitioning,
{\em Technical Report}, Faculty of Mathematics, University of Waterloo,
CORR 92-25, August 1992.

\bibitem{gjs} M.R. Garey, D.S. Johnson and L. Stockmeyer,
Some simplified NP-complete graph problems,
{\em Theoretical Computer Science} 1 (1976) 237-267.

\bibitem{hrvw} C. Helmberg, F. Rendl, R.J. Vanderbei and H. Wolkowicz,
{\em Technical Report}, Faculty of Mathematics, University of Waterloo,
SOR-93-15.
\end{thebibliography}





\end{document}

