Title: New Abilities and Limitations of Spectral Graph Bisection,
Abstract: Spectral based heuristics belong to well-known commonly used methods which
determines provably minimal graph bisection or outputs "fail" when the
optimality cannot be certified. In this paper we focus on Boppana's algorithm
which belongs to one of the most prominent methods of this type. It is well
known that the algorithm works well in the random \emph{planted bisection
model} -- the standard class of graphs for analysis minimum bisection and
relevant problems. In 2001 Feige and Kilian posed the question if Boppana's
algorithm works well in the semirandom model by Blum and Spencer. In our paper
we answer this question affirmatively. We show also that the algorithm achieves
similar performance on graph classes which extend the semirandom model.
Since the behavior of Boppana's algorithm on the semirandom graphs remained
unknown, Feige and Kilian proposed a new semidefinite programming (SDP) based
approach and proved that it works on this model. The relationship between the
performance of the SDP based algorithm and Boppana's approach was left as an
open problem. In this paper we solve the problem in a complete way by proving
that the bisection algorithm of Feige and Kilian provides exactly the same
results as Boppana's algorithm. As a consequence we get that Boppana's
algorithm achieves the optimal threshold for exact cluster recovery in the
\emph{stochastic block model}. On the other hand we prove some limitations of
Boppana's approach: we show that if the density difference on the parameters of
the planted bisection model is too small then the algorithm fails with high
probability in the model.