New Abilities and Limitations of
Spectral Graph Bisection
Martin R. Schuster1 and Maciej Liśkiewicz1

arXiv:1701.01337v2 [] 28 Apr 2017

1

Institute of Theoretical Computer Science, University of Lübeck, Germany

Spectral based heuristics belong to well-known commonly used methods which
determines provably minimal graph bisection or outputs “fail” when the optimality
cannot be certiﬁed. 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 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 aﬃrmatively.
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 semideﬁnite 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 stochastic block model. On
the other hand we prove some limitations of Boppana’s approach: we show that if
the density diﬀerence on the parameters of the planted bisection model is too small
then the algorithm fails with high probability in the model.

1 Introduction
The minimum graph bisection problem is one of the classical NP-hard problems [23]: for an
undirected graph G the aim is to partition the set of vertices V = {1, . . . , n} (n even) into
two equal sized sets, such that the number of cut edges, i.e. edges with endpoints in diﬀerent
bisection sides, is minimized. The bisection width of a graph G, denoted by bw(G), is then the
minimum number of cut edges in a bisection of G. Due to practical signiﬁcance in VLSI design,
image processing, computer vision and many other applications (see [31, 5, 46, 30, 32, 39])
and its theoretical importance, the problem has been the subject of a considerable amount of
research from diﬀerent perspectives: approximability [38, 4, 21, 20, 29], average-case complexity

1

[10], and parameterized algorithms [34, 44] including the seminal paper in this ﬁeld by Cygan
et al. [16] showing that the minimum bisection is ﬁxed parameter tractable.
In this paper we consider polynomial-time algorithms that for an input graph either output
the provable minimum-size bisection or “fail” when the optimality cannot be certiﬁed. The
methods should work well for all (or almost all, depending on the model) graphs of particular
classes, i.e. provide for them a certiﬁed optimum bisection, while for irregular, worst case
instances the output can be “fail”, what is justiﬁable. We investigate two well-studied graph
models: the planted bisection model and its extension the semirandom model which are widely
used to analyze and benchmark graph partitioning algorithms. We refer to [10, 17, 9, 6, 15,
19, 11, 35, 8, 12, 33] to cite some of the relevant works. Moreover, we consider the regular
graph model introduced of Bui et al. [10] and a new extension of the semirandom model. For
a (semi)random model we say that some property is satisﬁed with high probability (w.h.p.) if
the probability that the property holds tends to 1 as the number of vertices n → ∞.
In the planted bisection model, denoted as Gn (p, q) with parameters 1 > p = p(n) ≥ q(n) =
q > 0, the vertex set V = {1, . . . , n} is partitioned randomly into two equal sized sets V1
and V2 , called the planted bisection. Then for every pair of vertices do independently: if both
vertices belong to the same part of the bisection (either both belong to V1 or both belong to V2 )
then include an edge between them with probability p; If the two vertices belong to diﬀerent
parts, then connect the vertices by an edge with probability q. In the semirandom model
for graph bisection [19], initially a graph G is chosen at random according to model Gn (p, q).
Then a monotone adversary is allowed to modify G by applying an arbitrary sequence of the
following monotone transformations: (1) The adversary may remove from the graph any edge
crossing a minimum bisection; (2) The adversary may add to the graph any edge not crossing
the bisection. Finally, in the regular random model, denoted as Rn (r, b), with r = r(n) < n
and b = b(n) ≤ (n/2)2 , the probability distribution is uniform on the set of all graphs on V
that are r-regular and have bisection width b.
The planted bisection model was ﬁrst proposed in the sociology literature [28] under the
name stochastic block model to study community detection problems in random graphs. In
this setting, the planted bisection V1 , V2 (as described above) models latent communities in
a network and the goal here is to recover the communities from the observed graph. In the
general case, the model allows some errors by recovering, multiple communities, and also that
p(n) < q(n). The community detection problem on the stochastic block model has been subject
of a considerable amount of research in physics, statistics and computer science (see e.g. [1, 36]
for current surveys). In particular, an intensive study has been carried out on providing lower
bounds on |p − q| to ensure recoverability of the planted bisection.
The main focus of our work is the bisection algorithm proposed by Boppana [9]. Though
introduced almost three decades ago, the algorithm belongs still to one of the most important
heuristics in this area. However, several basic questions concerning the algorithm’s performance remain open. Using a spectral based approach, Boppana constructs an implementable
algorithm which, assuming the density diﬀerence
p
√
(1)
p − q ≥ c p ln n/ n for a certain constant c > 0
bisects Gn (p, q) optimally w.h.p. (certifying the optimality of the solutions). Remarkably, for a
long time this was the largest subclass of graphs Gn (p, q) for which a minimum bisection could
be found. Since under the assumption (1) the planted bisection is minimum w.h.p., Boppana’s
algorithm solves the recovery problem for the stochastic block model with two communities.

2

Boppana’s algorithm works well also on the regular graph model Rn (r, b), assuming that
r ≥ 6 and b ≤ o(n1−1/⌊(r/2+1)/2⌋ ).

(2)

In this paper we investigate the problem if, under assumption (1), Boppana’s algorithm
works well for the semirandom model. This question was posed by Feige and Kilian in [19] and
remained open so far. In our work we answer the question aﬃrmatively. We show also that
Boppana’s algorithm provides the same results as the algorithm proposed currently by Hajek,
Wu, and Xu [26]. As a consequence we get that Boppana’s algorithm achieves the optimal
threshold for exact recovery in the stochastic block model with parameters p = α log(n)/n
and q = β log(n)/n. On the other hand we show some limitations of the algorithm. One of
the main results
in this direction is that the density diﬀerence (1) is tight: we prove that if
√
√
p − q ≤ o( p · ln n/ n) then the algorithm fails on Gn (p, q) w.h.p.
Our Results. The motivation of our research was to systematically explore graph properties
which guarantee that Boppana’s algorithm outputs a certiﬁed optimum bisection. Due to [9]
we know that random graphs from Gn (p, q) and Rn (r, b) satisfy such properties w.h.p. under
assumptions (1) and (2) on p, q, r, and b as discussed above. But, as we will see later, the
algorithm works well also for instances which deviate signiﬁcantly from such random graphs.
Our ﬁrst technical contribution is a modiﬁcation of the algorithm to cope with graphs of
more than one optimum bisection, like e.g. hypercubes. The algorithm proposed originally by
Boppana does not manage to handle such cases. Our modiﬁcation is useful to work on wider
classes of graphs.
In this paper we introduce a natural generalization of the semirandom model of Feige and
Kilian [19]. Instead of Gn (p, q), we start with an arbitrary initial graph model Gn , and then
apply a sequence of the transformations by a monotone adversary as in [19]. We denote such
a model by A(Gn ). One of our main positive results is that if Boppana’s algorithm outputs
the minimum-size bisection for graphs in Gn w.h.p., then the algorithm ﬁnds a minimum
bisection w.h.p. for the adversarial graph model A(Gn ), too. As a corollary, we get that under
assumption (1), Boppana’s algorithm works well in the semirandom model, denoted here as
A(Gn (p, q)), and, assuming (2), in A(Rn (r, b)) – the semirandom regular model. This solves
the open problem posed by Feige and Kilian in [19]. To the best of our knowledge, Boppana’s
algorithm is the only method known so far, that ﬁnds (w.h.p.) provably optimum bisections
on all of the above random graph classes.
Since the behavior of the algorithm on the (common) semirandom model A(Gn (p, q)) remained unknown so far, Feige and Kilian proposed in [19] a new semideﬁnite programming
(SDP) based approach which works for semirandom graphs, assuming (1). The relationship
between the performance of the SDP based algorithm and Boppana’s approach was left in
[19] as an open problem. Feige and Kilian conjecture that for every graph G, their objective
function hp (G) to certify the bisection optimality and the lower bound computed in Boppana’s
algorithm give the same value. In our paper we answer this question aﬃrmatively. To compare the algorithms, we provide a primal SDP formulation for Boppana’s approach and prove
that it is equivalent to the dual SDP of Feige and Kilian. Next we give a dual program to
the primal formulation of Boppana’s algorithm and prove that the optima of the primal and
dual programs are equal to each other. Note that unlike linear programming, for semideﬁnite
programs there may be a duality gap. Thus, we show that the bisection algorithm of Feige
and Kilian provides exactly the same results as Boppana’s algorithm. However, an important
advantage of the spectral method by Boppana over the SDP based approach by Feige and

3

Kilian is that the spectral method is practically implementable reducing the bisection problem
for graphs with n vertices to computing minima of a convex function of n variables while the
algorithm in [19] needs to solve a semideﬁnite program over n2 variables.
From the result that the method by Feige and Kilian is equivalent to Boppana’s we get,
as a consequence, that Boppana’s algorithm achieves the sharp threshold for exact cluster
recovery in the stochastic block model which has been obtained recently by Abbe et al. [2] and
independently by Mossel et al. [37]. In [2, 37] it is proved that in the (binary) stochastic
√ 2block
√
model, with p = α log(n)/n and q = β log(n)/n for ﬁxed constants α 6= β, if ( α − β) > 2,
the planted clusters can be exactly recovered
(up to a permutation of cluster indices) with
√
√
probability converging to one; if ( α − β)2 < 2, no algorithm can exactly recover the clusters
with probability converging to one. Note, that the choice of p and q is well justiﬁed: Mossel
et al. show that if q < p = log(n)/n then the exact recovery is impossible for these parameters.
In [26] Hajek√et al. proved that the SDP of Feige and Kilian achieves the optimal threshold,
√
i.e. if ( α − β)2 > 2 then the SDP reconstructs communities w.h.p. From our result we get,
that Boppana’s algorithm achieves the threshold, too.
To analyze limitations of the spectral approach we provide structural properties of the space
of feasible solutions searched by the algorithm. This allows us to prove that if an optimal
bisection contains some forbidden subgraphs, then Boppana’s algorithm fails. Using these
tools, we were able to show that if the density diﬀerence p − q is asymptotically smaller than
√
√
p · ln n/ n then Boppana’s algorithm fails to determine a certiﬁed optimum bisection on
Gn (p, q) w.h.p. Note that our impossibility result is not a direct consequence of the lower
bound
√ for the exact cluster recovery discussed above. For example, for q = O(1)/n and
p = log n/n from Mossel et al. [37] we know that for these parameters the exact recovery is
impossible but obviously this does not imply that determining of a certiﬁed optimum bisection
is impossible either.
Related Works. Spectral partitioning goes back to Fiedler [22], who ﬁrst proposed to use
eigenvectors to derive partitions. Spielman and Teng e.g. showed, that spectral partitioning
works well on planar graphs [40, 41], although there are also graphs on which purely spectral
algorithms perform poorly, as shown by Guattery and Miller [25].
Also other algorithms have been proven to work on the planted bisection model. Condon
and Karp [15] developed a linear time algorithm for the more general l-partitioning problem.
Their algorithm ﬁnds the optimal partition with probability 1 − exp(−nΘ(ε) ) in the planted
bisection model with parameters satisfying p − q = Ω(1/n1/2−ε ). Carson and Impaglizzo [11]
show that a hill-climbing algorithm is able to ﬁnd the planted bisection w.h.p. for parameters
p − q = Ω((ln3 n)/n1/4 ). Dyer and Frieze [17] provide a min-cut via degrees heuristic that,
assuming n(p − q) = Ω(n) ﬁnds and certiﬁes the minimum bisection w.h.p. Note, that the
density diﬀerence (1) assumed by Boppana still outperforms the above ones. Moreover a
disadvantage of the methods against Boppana’s algorithm, except for the last one, is that
they do not certify the optimality of the solutions. In [35] McSherry describes a spectral
based heuristic that applied to G(p, q) ﬁnds a minimum bisection w.h.p if p and q satisfy
assumption (1) but it does not certify the optimality. Importantly, the algorithms above,
similarly as Boppana’s method, solve the recovery problem for the stochastic block model with
two communities.
In [12] Coja-Oghlan developed a new spectral-based algorithm which, on the planted partition model Gn (p, q), enables for a wider range of parameters than (1), certifying the optimality

4

p
√
of its solutions. The algorithm [12] assumes that p − q ≥ Ω( p ln(np)/ n). If the parameters p and q describe non-sparse graphs, this condition is essentially the same as Boppana’s
assumption. For sparse graphs, however, Coja-Oghlan’s constraint allows
√ a larger subclass.
For example, the algorithm works in Gn (p, q) for q = O(1)/n and p = log n/n. Due to results presented in our paper we know that Boppana’s algorithm fails w.h.p. for such graphs.
Interestingly, the condition on the density diﬀerence by Coja-Oghlan allows graphs for which
the minimum bisection width is strictly smaller than the width of the planted bisection w.h.p.
However, a drawback of Coja-Oghlan’s algorithm is that to work well in the planted bisection
model with unknown parameters p and q, the algorithm has to learn the parameters since it
is based on the knowledge of values p and q. Also the performance of the algorithm on other
families, like e.g. semirandom graphs and the regular random graphs Rn (r, b), is unknown. Recent research by Coja-Oghlan et al. [14] contributes to a better understanding of the planted
bisection model and average case behavior of a minimum bisection.
The paper is organized as follows. The next section contains an overview over Boppana’s
algorithm. In Section 3 we propose a modiﬁcation of the algorithm to deal with non-unique
optimum bisections. In Section 4 we deﬁne the adversarial graph model and show, that Boppana’s algorithm works well on this class. Next we develop a new analysis of the algorithm
and use it to show some limitations of the method. Finally, in Section 6 we compare the
algorithm to the SDP approach of Feige and Kilian. We conclude the paper with a discussion.
The proofs of most of the propositions presented in Sections 2 through 6 are moved to the
appendix (Section 8).

2 Boppana’s Graph Bisection Algorithm
In this section we ﬁx deﬁnitions and notations used in our paper and we recall Boppana’s
algorithm and known facts on its performance. We need the details of the algorithm to describe
its extension in the next section. For a given graph G = (V, E), with V = {1, . . . , n}, Boppana
deﬁnes a function f for all real vectors x, d ∈ Rn as
P
P
1−x x
(3)
f (G, d, x) = {i,j}∈E 2i j + i∈V di (x2i − 1).
P
Call by S ⊂ Rn the subspace of all vectors x ∈ Rn , with i xi = 0. Based on f , the function
g′ is deﬁned as follows
g′ (G, d) =
min
f (G, d, x),
(4)
kxk2 =n,x∈S

wherePkxk denotes L2 norm of x. Vector x is named a bisection vector if x ∈ {+1, −1}n
and
i xi = 0. Such x determines a bisection of G of the cut width denoted as cw(x) =
P
1−xi xj
. For a bisection vector x the function f takes the value (3) regardless of d.
{i,j}∈E
2
Minimization over all such x would give the minimum bisection width. Since g′ uses a relaxated
constraint we get g′ (G, d) ≤ bw(G) where, recall, bw(G) denotes the bisection width of G. To
improve the bound, Boppana tries to ﬁnd some d which leads to a minimal decrease of the
function value of g′ compared to the bisection width:
h(G) = maxn g′ (G, d).
d∈R

(5)

It is easy to see that for every graph G we have h(G) ≤ bw(G).
In order to compute g′ eﬃciently, Boppana expresses the function in spectral terms. To
describe this we need some deﬁnitions. Let I denote the n-dimensional identity matrix and

5

let P = I − n1 J be the projection matrix which projects a vector x ∈ Rn to the projection
P x of vector x into the subspace S. Here, J denotes an n × n matrix of ones. For a matrix
B ∈ Rn×n , the matrix BS = P BP projects a vector x ∈ Rn to S, then applies B and projects
n×n and d ∈ Rn we denote the sum of B’s elements
the result again
P into S. Further, for B ∈ R
as sum(B) = ij Bij and by diag(d) we denote the n × n diagonal matrix D with the entries
of the vector d on the main diagonal, i. e. Dii = di .
Now assume B ∈ Rn×n is symmetric and let BS = P BP . Denote by Rn6=c1 the real space
Rn without the subspace spanned by the identity vector 1, i. e. Rn6=c1 = Rn \ {c1 : c ∈ R}. We
deﬁne λ(BS ) = maxx∈Rn6=c1

xT BS x
kxk .

It is easy to see that if λ(BS ) ≥ 0 then

xT BS x
(6)
x∈R
kxk
i. e. λ(BS ) is the largest eigenvalue of the matrix BS . Vectors x that attain the maximum are
exactly the eigenvectors corresponding to the largest eigenvalue λ(BS ) of BS .
Let G be an undirected graph with n vertices and adjacency matrix A. Let further d ∈ Rn
be some vector and let B = A + diag(d), then we deﬁne
sum(B) − nλ(BS )
g(G, d) =
.
4
In [9] it is shown that function g ′ can be expressed as g′ (G, d) = g(G, −4d). Since in the
deﬁnition of h in (5) we maximize over all d, we can conclude that
sum(A + diag(d)) − nλ((A + diag(d))S )
.
(7)
h(G) = maxn g(G, d) = maxn
d∈R
d∈R
4
Boppana’s algorithm that ﬁnds and certiﬁes an optimal bisection, works as follows:
λ(BS ) = maxn

Algorithm 1: Boppana’s Algorithm
Input : Graph G with adjacency matrix A.
1 Compute h(G): Numerically ﬁnd a vector dopt which maximizes g(G, d). Let
P
D = diag(dopt ). Use constraint i dopt
= 2|E| to ensure λ((A + D)S ) > 0;
i
2 Construct a bisection: Let x be an eigenvector corresponding to the eigenvalue
λ((A + D)S ). Construct a bisection vector x̂Pby splitting at the median x̄ ofPx, i.e. let
x̂i = +1 if xi ≥ x̄ and x̂i = −1 if xi < x̄. If i x̂i > 0, move (arbitrarily) 12 i x̂i
vertices i with xi = x̄ to part −1 letting x̂i = −1;
3 Output x̂; If cw(x̂) = h(G) output “optimum bisection” else output “fail”.
One can prove that g is concave and hence, the maximum in Step 1 can be found in polynomial time with arbitrary precision [24]. To analyse the algorithm’s performance, Boppana
proves the following, for a suﬃciently large constant c > 0:
Theorem
2.1 (Boppana [9]). Let G be a random graph from Gn (p, q), and let p − q ≥
√
√
c( p ln n/ n). Then with probability 1 − O(1/n), the bisection width of G equals h(G).
From this result one can conclude that the value h(G) computed by the algorithm is, w.h.p.,
equal to the optimal bisection width of G. However, to guarantee that the algorithm works
well one needs additionally to show that it also ﬁnds an optimal bisection:
√
√
Theorem 2.2. For random graphs G from Gn (p, q), with p − q ≥ c( p ln n/ n), Boppana’s
algorithm certifies the optimality of h(G) revealing w.h.p. the bisection vector x̂ of cw(x̂) =
h(G).
To prove this theorem one ﬁrst has to revise carefully the proof of Theorem 2.1 in [9] and

6

show that w.h.p. the multiplicity of the largest eigenvalue of the matrix (A + D)S in Step 1
is 1. This was observed already in [7]. Next we need the following property:
Lemma
2.3. Let G be a graph with h(G) = bw(G) and let dopt ∈ Rn s. t. g(G, dopt ) = bw(G)
P opt
and i di ≥ 4 bw(G) − 2|E|. Denote further by B opt = A + diag(dopt ). Then every optimum
bisection vector y is an eigenvector of BSopt corresponding to the largest eigenvalue λ(BSopt ).
(The proof of Lemma 2.3, as the proofs of most of the remaining propositions presented in
this paper, are given in Section 8.) This completes the proof that the algorithm works well on
random graphs from Gn (p, q).

3 Certifying Non-Unique Optimum Bisections
From the previous section we know that if the bound h(G) is tight and the bisection of minimum
size is unique, or more precisely the multiplicity of the largest eigenvector of BS is 1, Boppana’s
algorithm is able to certify the optimality of the resulting bisection. We say that a graph G
has a unique optimum bisection if there exists a unique, up to the sign, bisection vector x
such that cw(x) = cw(−x) = bw(G). In this paper we investigate families of graphs, diﬀerent
than random graphs Gn (p, q), for which the Boppana’s approach works well. To this aim we
ﬁrst need to show a modiﬁcation which handles cases such that h(G) = bw(G) but for which
no unique bisection of minimum size exists. As we will see later hypercubes satisfy these
two conditions. We present our algorithm below. Note that if the multiplicity of the largest
eigenvalue of BSopt is 1, then the algorithm outputs the same result as in the original algorithm
by Boppana.
Algorithm 2: Boppana’s Algorithm Certifying Non-Unique Optimum Bisections
Input : Graph G with adjacency matrix A.
1 Perform Step 1 of Algorithm 1; Let x be an eigenvector corresponding to the eigenvalue
λ((A + D)S ) and let k be the multiplicity of the largest eigenvalue of (A + D)S ;
2 If k = 1 then construct a bisection vector x̂ by splitting at the median x̄ as in Step 2 of
Algorithm 1; Next output x̂ and if cw(x̂) = h(G) output “optimum bisection” else
output “fail”; If k > 1 then perform the steps below;
3 Let M ∈ Rn×k be the matrix with k linear independent eigenvectors corresponding to
this largest eigenvalue; Transform the matrix to the reduced column echelon form, i. e.
there are k rows which form an identity matrix, s.t. M still spans the same subspace;
4 Brute force: for every combination of k coeﬃcients from {+1, −1} take the linear
combination of the k vectors of M with the coeﬃcientsPand verify if the resulting
vector x is a bisection vector, i.e. x ∈ {+1, −1}n with i xi = 0. If yes and if
cw(x) = h(G) then output x and continue. This needs 2k iterations;
5 If in Step 4 no bisection vector x is given then output “fail”.
Theorem 3.1. If h(G) = bw(G) then the algorithm above reconstructs all optimal bisections.
Every achieved bisection vector corresponds to an optimal bisection.
The eigenvalues for the family of hypercubes are explicitly known [27]. Hence, we can
verify that the bound h(G) is tight and Boppana’s algorithm with the modiﬁcation above
works, i.e. ﬁnds an optimal bisection. For a hypercube Hn with n vertices we have h(Hn ) =
g(Hn , (2 − log n)1) = n/2 = bw(Hn ). Since the hypercube with n vertices has log n optimal
bisections and the largest eigenspace of BS has multiplicity log n, the brute force part in our

7

modiﬁcation of Boppana’s algorithm results in a linear factor of n for the overall runtime.
Thus, the algorithm runs in polynomial time. In the next section we will extend this result to
an adversarial model based on hypercubes and show, that Boppana’s algorithm works on that
model as well.

4 Bisections in Adversarial Models
We introduce the adversarial model, denoted by A(Gn ), as a generalization of the semirandom
model in the following way. Let Gn be a graph model, i.e. a class of graphs with distributions
over graphs of n nodes (n even). In the model A(Gn ), initially a graph G is chosen at random
according to Gn . Let (Y1 , Y2 ) be a ﬁxed, but arbitrary optimal bisection of G. Then, similarly
as in [19], a monotone adversary is allowed to modify G by applying an arbitrary sequence of
the following monotone transformations:
1. The adversary may remove from the graph any edge {u, v} crossing a minimal bisection
(u ∈ Y1 and v ∈ Y2 );
2. The adversary may add to the graph any edge {u, v} not crossing the bisection (u, v ∈ Y1
or u, v ∈ Y2 ).
For example, A(Gn (p, q)) is the semirandom model as deﬁned in [19].
We will prove that Boppana’s algorithm works well for graphs from adversarial model A(Gn )
if the algorithm works well for Gn . First we show that, if the algorithm is able to ﬁnd an optimal
bisection size of a graph, we can add edges within the same part of an optimum bisection and
that we can remove cut edges, and the algorithm will still work. This solves the open question
of Feige and Kilian [19].
Note that the result follows alternatively from Corollary 6.4 (presented in Section 6) that the
SDPs of [19] are equivalent to Boppana’s optimization function and form the property proved
in [19] that the objective function of the dual SDP of Feige and Kilian preserves minimal
bisection regardless of monotone transformations. The aim of this section is to give a direct
proof of this property for Boppana’s algorithm.
Theorem 4.1. Let G = (V, E) be a graph with h(G) = bw(G). Consider some optimum
bisection Y1 , Y2 of G.
1. Let u and v be two vertices within the same part, i.e. u, v ∈ Y1 or u, v ∈ Y2 , and let
G′ = (V, E ∪ {{u, v}}). Then h(G′ ) = bw(G′ ).
2. Let u and v be two vertices in different parts, i.e. u ∈ Y1 and v ∈ Y2 , with {{u, v}} ∈ E
and let G′ = (V, E \ {{u, v}}). Then h(G′ ) = bw(G) − 1 = bw(G′ ).
Sketch of proof. In order to prove the ﬁrst part of the theorem, i.e. when we add an edge {u, v},
let A and A′ denote the adjacency matrices of G and G′ , respectively. It holds A′ = A + A∆
∆
with A∆
uv = Avu = 1 and zero everywhere else. The main idea is now, that we can derive a
new optimal correction vector d′ for G′ based on the optimal correction vector dopt for G. We
set d′ = dopt + d∆ with
(
−1 if i = u or i = v,
d∆
i =
0
else.
The known changes in the adjacency matrix as well as the derived correction vector allow
us to compute g(G′ , d′ ) and to show that g(G′ , d′ ) = bw(G′ ). The proof of the second part of
the theorem works analogously. The complete proof can be found in the appendix.

8

Theorem 4.2. If Boppana’s algorithm finds a minimum bisection for a graph model Gn w.h.p.,
then it finds a minimum bisection w.h.p. for the adversarial model A(Gn ), too.
As a direct consequence, we obtain the following corollary regarding the semirandom graph
model considered by Feige and Kilian:
Corollary 4.3. Under assumption (1) on p and q, Boppana’s algorithm computes the minimum bisection in A(Gn (p, q)), i.e. in the semirandom model, w.h.p.
In [9], Boppana also considers random regular graphs Rn (r, b), where a graph is chosen
uniformly over the set of all r-regular graphs with bisection width b. He shows that his
algorithm works w.h.p. on this graph under the assumption that b = o(n1−1/⌊(r+1)/2⌋ ). We can
now deﬁne the semirandom regular graph model as adversarial model A(Rn (r, b)). Applying
Theorem 4.2, we obtain
Corollary 4.4. Under assumption (1) on p and q, Boppana’s algorithm computes the minimum bisection in the semirandom regular model w.h.p.
Theorem 4.2 can also be applied on deterministic graph classes, e.g. the class of hypercubes.
We then obtain:
Corollary 4.5. Boppana’s algorithm (with our modification for non-unique bisections) finds
an optimal bisection on adversarial modified hypercubes.

5 The Limitations of the Algorithm
Boppana shows, that his algorithm works well on some classes of random graphs. However,
we do not know which graph properties force the algorithm to fail. For example, for the
considered planted bisection model, we require a small bisection width. On the other hand, as
we have seen in Section 3 Boppana’s algorithm works for the hypercubes and their semirandom
modiﬁcations – graphs that have large minimum bisection sizes.
In the following, we present newly discovered structural properties from inside the algorithm,
which provide a framework for a better analysis of the algorithm itself. Let y be a bisection
vector of G. We deﬁne
d(y) = − diag(y)Ay.
(8)
(y)

An equivalent but more intuitive characterization of d(y) is the following: di is the diﬀerence
between the number of adjacent vertices in other partition as vertex i and the number of
adjacent vertices in same partition as i.
Lemma 5.1. Let G be a graph with h(G) = bw(G) and assume there is more than one optimum
bisection in G. Then (up to constant translation vectors c1) there exists a unique vector dopt
with g(G, dopt ) = bw(G). Additionally, for every bisection vector y of an arbitrary optimum
bisection in G there exists a unique α(y) and the corresponding d(y) , with g(G, d(y) + α(y) y) =
bw(G).
′
Thus, if there are two optimum bisections representing by y and y ′ with d(y) 6= d(y ) , then
the diﬀerence of the d-vectors in component i is only dependent on yi and yi′ , since we have
′
d(y) − d(y ) = β ′ y ′ − βy for some constants β and β ′ . This structural property allows us to show
the following limitation for the sparse planted partition model Gn (p, q).
Theorem 5.2.√The algorithm of Boppana fails w.h.p. in the subcritical phase from [12], defined
as n(p − q) = np · γ ln n, for real γ > 0.

9

In the planted partition model Gn (p, q), if the graphs are dense, e.g. p = 1/nc for a constant
c with 0 < c < 1, the constraints for the density diﬀerence p − q assumed in Boppana’s [9]
and Coja-Oghlan’s [12] algorithms are essentially the same. However for sparse
√ graphs, e.g.
log n/n satisfy
such that q = O(1)/n, the situation
changes
drastically.
Now,
e.g.
p
=
p
√
Coja-Oghlan’s constraint p − q ≥ Ω( p ln(pn)/ n) but the condition on the diﬀerence p − q
assumed by Boppana is not true any more. Theorem 5.2 shows that Boppana’s algorithm
indeed fails under this setting.
The proof of this theorem relies on the following observation, which can be derived from our
newly discovered structural properties from above.
Lemma 5.3. Let G be a graph with h(G) = bw(G) and let (Y1 , Y−1 ) be an arbitrary optimal
bisection. Then, for each pair of vertices vi ∈ Yi , i ∈ {1, −1}, not connected by an edge
({vi , v−i } 6∈ E), we have: If e(vi , Yi ) = e(vi , Y−i ) for i ∈ {1, −1} (the vertices have balanced
degree), then N (vi ) = N (v−i ), i.e. both vertices have the same neighbors.
I.e. if we have two balanced vertices in diﬀerent parts of an optimal bisection, not connected
by an edge, then the two vertices must have the same neighborhood as a necessary criterion
for Boppana’s algorithm to work. In the subcritical phase in Theorem 5.2, there exist most
likely many of such pairs of vertices, but they are unlikely to have all even the same degree.
We can also provide forbidden substructures, which make Boppana’s algorithm fail. This is
e.g. the case, when the graph contains a path segment located on an optimal bisection:
Corollary 5.4. Let G be a graph, as illustrated in Fig. 1 (left), with n ≥ 10 vertices containing
a path segment {u′ , u}, {u, w}, {w, w′ }, where u and w have no further edges. If there is an
optimal bisection y, s. t. yu = yu′ = +1 and yw = yw′ = −1 (i. e. {u, w} is a cut edge), then
h(G) < bw(G).
To prove this corollary, we use the more general but more technical Lemma 8.3 (in Appendix)
with parameters C̃+1 = {u} and C̃−1 = {w}.

. . . u′

u

w

w′ . . .

. . . u′1

u1

w1

w1′ . . .

. . . u′2

u2

w2

w2′ . . .

Figure 1: Forbidden graph structures as in Corollary 5.4 (left) and in Corollary 5.5 (right).
The result can also be applied for 2 × c lattices:
Corollary 5.5. Let G be a graph with n ≥ 10c vertices containing a 2 × c lattice with vertices
ui and wi , as illustrated in Fig. 1 (right). (The construction is similar to the corollary above,
but now we have a lattice instead of a single cut edge.) If there is an optimal bisection y, s. t.
yui = yu′i = +1 and ywi = ywi′ = −1, then h(G) < bw(G).
Futhermore, the algorithm fails if there are isolated vertices in both parts of an optimal
bisection:
Theorem 5.6. Let G be a graph with h(G) = bw(G). Let G′ be the graph G with two additional
isolated vertices, then h(G′ ) ≤ h(G)− 4 bw(G)
. (Note: G has n vertices and G′ has n+2 vertices.)
n2

10

6 SDP Characterizations of the Graph Bisection Problem
Feige and Kilian express the minimum-size bisection problem for an instance graph G as a
semideﬁnite programming problem (SDP) with solution hp (G) and prove that the function
hd (G), which is the solution to the dual SDP, reaches bw(G) w.h.p. Since bw(G) ≥ hp (G) ≥
hd (G), they conclude that hp (G) as well reaches bw(G) w.h.p. The proposed algorithm computes hp (G) and reconstructs the minimum bisection of G from the optimum solution of the
primal SDP. The authors conjecture in [19, Sec. 4.1.] the following: ”Possibly, for every graph
G, the function hp (G) and the lower bound h(G) computed in Boppana’s algorithm give the
same value, making the lemma that hp (G) = bw(G) w.h.p. a restatement of the main theorem
of [9]. In this section we answer this question aﬃrmatively.
The semideﬁnite programming approach for optimization problems was studied by Alizadeh [3],
who as ﬁrst provided an equivalent SDP formulation of Boppana’s algorithm. Before we give
an SDP introduced by Feige an Kilian, we recall brieﬂy some basic deﬁnitions and provide an
SDP formulation for Boppana’s approach. On the space Rn×m of n P
× m matrices,
we denote
P
by A • B an inner product of A and B deﬁned as A • B = tr(AB) = ni=1 m
A
B
ij
ij , where
j=1
tr(C) is the trace of the (square) matrix C. Let A be an n × n symmetric real matrix, then
A is called symmetric positive semideﬁnite (SPSD) if A is symmetric, i.e. AT = A, and for all
real vectors v ∈ Rn we have v T Av ≥ 0. This property is denoted by A  0. Note that the
eigenvalues of a symmetric matrix are real.
For given real vector c ∈ Rn and m + 1 symmetric matrices F0 , . . . , Fm ∈ Rn×n an SDP over
variables x ∈ Rn is deﬁned as
m
X
xi Fi  0.
(9)
min cT x subject to F0 +
x

i=1

The dual program associated with the SDP (for details see e.g. [45]) is the program over the
variable matrix Y = Y T ∈ Rn×n :
max −F0 • Y
Y

subject to ∀i : Fi • Y = ci

and

Y  0.

(10)

It is known that the optimal value of the maximization dual SDP is never larger than the
optimal value of the minimization primal counterpart. However, unlike linear programming,
for semideﬁnite programs there may be a duality gap, i.e. the primal and/or dual might not
attain their respective optima.
To prove that for any graph G Boppana’s function h(G) gives the same value as hp (G) we
formulate the function h as a (primal) SDP. We provide also its dual program and prove that
the optimum solutions of primal and dual are equal in this case. Then we show that the dual
formulation of the Boppana’s optimization is equivalent to the primal SDP deﬁned by Feige
and Kilian [19].
Below, G = (V, E) denotes a graph, A the adjacency matrix of G and for a given vector d,
as usually, let D = diag(d), for short. We provide the SDP for the function h (Eq. (7)) that
diﬀer slightly from that one given in [3].
Proposition 6.1. For any graph G = (V, E), the objective function
sum(A + D) − nλ((A + D)S )
h(G) = maxn
d∈R
4

11

maximized by Boppana’s algorithm can be characterized as an SDP as follows:

 p(G) = min (nz − 1T d) subject to
n
z∈R,d∈R

 zI − A +

JA+AJ
n

−

sum(A)J
n2

−D+

1dT +d1T
n

−

sum(D)J
n2

(11)

 0,

1
with the relationship h(G) = |E|
2 − 4 p(G). The dual program to the program (11) can be
expressed as follows:



P
P
P
P
P

d(G) = max A • Y − n1 j deg(j) i yij − n1 i deg(i) j yij + n12 i,j yij


Y ∈Rn×n





 subject to
P
(12)
i yii = n,



P
P
P


∀i yii − n1 j yji − n1 j yij + n12 k,j ykj = 1,




Y  0.

Using these formulations we prove that the primal and dual SDPs attain the same optima.
Theorem 6.2. For the semidefinite programs of Proposition 6.1 the optimal value p∗ of the
primal SDP (11) is equal to the optimal value d∗ of the dual SDP (12). Moreover, there exists
a feasible solution (z, d) achieving the optimal value p∗ .
Proof. Consider the primal SDP (11) of Boppana in the form
min

z∈R,d∈Rn

z

s.t.

zI − M (d)  0,

T

with M (d) = P (A + diag(d))P − 1n d I and, recall, P = I − Jn . Note that this formulation is
equivalent to (11), as we have shown in the proof of Proposition 6.1. We show that this primal
SDP problem is strictly feasible, i.e. that there exists an z ′ and an d′ with z ′ I − M (d′ ) ≻ 0.
To this aim we choose an arbitrary d′ and then some z ′ > λ(M (d′ )). From [45, Thm. 3.1], it
follows that the optima of primal and dual obtain the same value.
To prove the second part of the theorem, i.e. there exists a feasible solution achieving the
optimal value p∗ , consider the following. The function h(G) maximizes g(G, d) over vectors
d ∈ Rn , while d can be restricted to vectors of mean zero. The function g is convex and goes
to −∞ for vectors d with some component going to ∞. Thus, g reaches its maximum at some
ﬁnite dopt . Now we choose d = dopt and z = λ(M (dopt )). Clearly, this solution is feasible and
obtains the optimal value p∗ .
For a graph G = (V, E), Feige and Kilian express the minimum bisection problem as an SDP
over an n × n matrix Y as follows:
X
hp (G) = min hY (G) s.t.
∀i yii = 1,
yij = 0, and Y  0,
(13)
Y ∈Rn×n

where hY (G) =

P

1−yij
{i,j}∈E
2 .
i<j

i,j

For proving that the SDP takes as optimum the bisection width

w.h.p. on Gn (p, q), the authors consider the dual of their SDP:
!
|E| 1 X
s.t. M = −A − x0 J − diag(x)  0,
xi
+
hd (G) = maxn
x∈R
2
4

(14)

i

where A is the adjacency matrix of G. They show that the dual takes the value of the bisection
width w.h.p. and bounds the optimum of the primal SDP. Although we know that their SDP
and Boppana’s algorithm both work well on Gn (p, q), it was open so far how they are related

12

to each other. Below we answer this question showing that the formulations are equivalent.
We start with the following:
Theorem 6.3. The primal SDP (13) is equivalent to the dual SDP (12), with the relationship
1
hp (G) = |E|
2 − 4 d(G).
From Theorems 6.2 and 6.3 we get
Corollary 6.4. Let G be an arbitrary graph. Then for the lower bound h(G) of Boppana’s
algorithm and for the objective functions hp (G) of the primal SDP (13), resp. hd (G) of the
dual SDP (13) of Feige and Kilian [19] it is true
h(G) = hp (G) = hd (G).
Thus, the both algorithms provide for any graph G the same objective value. We want
to point out another important fact: the bisection algorithm proposed in [19] use an SDP
formulation, where the variables are a matrix with dimension n × n. Thus, there are n2
variables for a graph with n vertices. In contrast, Boppana’s algorithm uses n variables in the
convex optimization problem. If we consider the dual SDP, we again have only n + 1 variables.
However, due to Corollary 6.4, we can’t be better than Boppana’s algorithm.
Abbe et al. [2] and independently Mossel et al. [37] have shown, that there is a sharp
threshold phenomenon when considering the Gn (p, q) model with p = α log(n)/n and q =
β log(n)/n for ﬁxed constants
α, β, α > β. Exact recovery of the planted bisection is possible
√ 2
√
if and only if ( α − β) > 2 (see e.g. [37] for a formal deﬁnition of exact cluster recovery
problem). Hajek et al. [26] show, than an SDP equivalent to the one of Feige and Kilian achieves
this bound. Since, due to Corollary 6.4, we know that the SDP is equivalent to Boppana’s
algorithm, we conclude that also Boppana’s algorithm achieves the optimal threshold for ﬁnding
and certifying the optimal bisection in the considered model. We get:
Theorem 6.5. Let α and β, α > β, be constants. Consider the graph
Gn (p, q) with
√ model
√
2 > 2, Boppana’s
p = α log(n)/n and q = β log(n)/n. Then, as n → ∞,
if
(
α
−
β)
√
√
algorithm recovers the planted bisection w.h.p. If ( α − β)2 < 2, no algorithm is able to
recover the planted bisection w.h.p.
Proof. The second part of the theorem is exactly the statement from [2]. The ﬁrst part, i.e.
that Boppana’s algorithm √
is able to recover the bisection, follows from [26, Thm. 2]. Hajek et
√
al. show, that for ( α − β)2 > 2 the SDP of Feige and Kilian obtain the optimal solution.
Due to Theorem 6.3, the same holds for Boppana’s algorithm.

7 Discussion and Open Problems
Boppana’s spectral method is a practically implementable heuristic. Computing eigenvalues
and eigenvectors is well-studied and can be done very eﬃciently. Falkner, Rendl and Wolkowicz
[18] show in a numerical study that using spectral techniques for graph partitioning is very
robust and upper and lower bounds for the bisection width can be obtained such that the
relative gap is often just a few percentage points apart. In [43] and [42], Tu, Shieh and Cheng
present numerical experiments including results for Boppana’s algorithm. They verify that
the algorithm indeed has good average case behavior over certain probability distributions on
graphs. We conducted further experiments on the graph model Rn (r, b) which indicated, that
Boppana’s algorithm also works for r = 5, but not for r = 3 and r = 4. An interesting question

13

arising is, which properties of 3- and 4-regular graphs from the planted bisection model let the
algorithm fail.

References
[1] Emmanuel Abbe. Community detection and stochastic block models: recent developments.
arXiv preprint arXiv:1703.10146, 2017.
[2] Emmanuel Abbe, Afonso S Bandeira, and Georgina Hall. Exact recovery in the stochastic
block model. IEEE Transactions on Information Theory, 62(1):471–487, 2016.
[3] Farid Alizadeh. Interior point methods in semideﬁnite programming with applications to
combinatorial optimization. SIAM J. on Optimization, 5(1):13–51, 1995.
[4] Sanjeev Arora, David Karger, and Marek Karpinski. Polynomial time approximation
schemes for dense instances of np-hard problems. In Proc. of the 27th Annual ACM
Symposium on Theory of Computing (STOC), pages 284–293. ACM, 1995.
[5] Sandeep N Bhatt and Frank Thomson Leighton. A framework for solving vlsi graph layout
problems. Journal of Computer and System Sciences, 28(2):300–343, 1984.
[6] Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs.
Journal of Algorithms, 19(2):204–234, 1995.
[7] Robert D. Blumofe. Spectral methods for bisecting graphs. Unpublished Manuscript,
1993.
[8] Béla Bollobás and Alex D Scott. Max cut for random graphs with a planted partition.
Combinatorics, Probability and Computing, 13(4-5):451–474, 2004.
[9] Ravi B. Boppana. Eigenvalues and graph bisection: An average-case analysis. In Proc. of
the 28th Annual Symposium on Foundations of Computer Science (FOCS), pages 280–285.
IEEE Computer Society, 1987.
[10] T. N. Bui, S. Chaudhuri, F. T. Leighton, and M. Sipser. Graph bisection algorithms with
good average case behavior. Combinatorica, 7(2):171–191, 1987.
[11] Ted Carson and Russell Impagliazzo. Hill-climbing ﬁnds random planted bisections. In
Proc. of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages
903–909. SIAM, 2001.
[12] Amin Coja-Oghlan. A spectral heuristic for bisecting random graphs. In Proc. of the 17th
Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 850–859. SIAM,
2005.
[13] Amin Coja-Oghlan. Spectral techniques, semideﬁnite programs, and random graphs. Habilitationsschrift, Humboldt Universität zu Berlin, Institut für Informatik, 2005.
[14] Amin Coja-Oghlan, Charilaos Efthymiou, and Nor Jaafari. Local convergence of random
graph colorings. In Proc. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, (APPROX/RANDOM), volume 40 of LIPIcs, pages
726–737, 2015.

14

[15] Anne Condon and Richard M Karp. Algorithms for graph partitioning on the planted
partition model. Random Structures and Algorithms, 18(2):116–140, 2001.
[16] Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, MichalPilipczuk, and Saket Saurabh.
Minimum bisection is ﬁxed parameter tractable. In Proc. of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 323–332. ACM, 2014.
[17] Martin E. Dyer and Alan M. Frieze. The solution of some random np-hard problems in
polynomial expected time. Journal of Algorithms, 10(4):451–489, 1989.
[18] Julie Falkner, Franz Rendl, and Henry Wolkowicz. A computational study of graph partitioning. Mathematical Programming, 66(1-3):211–239, 1994.
[19] Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4):639–671, 2001.
[20] Uriel Feige and Robert Krauthgamer. A polylogarithmic approximation of the minimum
bisection. SIAM J. Computing, 31(4):1090–1118, April 2002.
[21] Uriel Feige, Robert Krauthgamer, and Kobbi Nissim. Approximating the minimum bisection size. In Proc. of the 32nd Annual ACM Symposium on Theory of Computing (STOC),
pages 530–536. ACM, 2000.
[22] Miroslav Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its
application to graph theory. Czechoslovak Mathematical Journal, 25(4):619–633, 1975.
[23] Michael R Garey, David S. Johnson, and Larry Stockmeyer. Some simpliﬁed np-complete
graph problems. Theoretical Computer Science, 1(3):237–267, 1976.
[24] M. Grötschel, L. Lovász, and A. Schrijver. The ellipsoid method and its consequences in
combinatorial optimization. Combinatorica, 1(2):169–197, 1981.
[25] Stephen Guattery and Gary L. Miller. On the quality of spectral separators. SIAM J.
Matrix Anal. Appl., 19(3):701–719, July 1998.
[26] Bruce Hajek, Yihong Wu, and Jiaming Xu. Achieving exact cluster recovery threshold via
semideﬁnite programming. IEEE Transactions on Information Theory, 62(5):2788–2797,
2016.
[27] Frank Harary, John P. Hayes, and Horng-Jyh Wu. A survey of the theory of hypercube
graphs. Computers and Mathematics with Applications, 15(4):277 – 289, 1988.
[28] Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109–137, 1983.
[29] Subhash Khot. Ruling out ptas for graph min-bisection, dense k-subgraph, and bipartite
clique. SIAM Journal on Computing, 36(4):1025–1071, 2006.
[30] Vivek Kwatra, Arno Schödl, Irfan Essa, Greg Turk, and Aaron Bobick. Graphcut textures:
image and video synthesis using graph cuts. ACM Transactions on Graphics (ToG),
22(3):277–286, 2003.

15

[31] Thomas Lengauer. Combinatorial algorithms for integrated circuit layout. Springer Science
& Business Media, 2012.
[32] Richard J Lipton and Robert Endre Tarjan. Applications of a planar separator theorem.
SIAM journal on computing, 9(3):615–627, 1980.
[33] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Approximation algorithms for semi-random partitioning problems. In Proc. of the 44th Annual ACM
Symposium on Theory of Computing (STOC), pages 367–384. ACM, 2012.
[34] Dániel Marx. Parameterized graph separation problems. Theoretical Computer Science,
351(3):394–406, 2006.
[35] Frank McSherry. Spectral partitioning of random graphs. In Foundations of Computer
Science, 2001. Proceedings. 42nd IEEE Symposium on, pages 529–537. IEEE, 2001.
[36] Cristopher Moore. The computer science and physics of community detection: Landscapes,
phase transitions, and hardness. arXiv preprint arXiv:1702.00467, 2017.
[37] Elchanan Mossel, Joe Neeman, and Allan Sly. Consistency thresholds for the planted
bisection model. In Proc. of the 47th ACM Symp. on Theory of Computing (STOC),
pages 69–75. ACM, 2015.
[38] Huzur Saran and Vijay V Vazirani. Finding k cuts within twice the optimal. SIAM J. on
Computing, 24(1):101–108, 1995.
[39] Kirk Schloegel, George Karypis, and Vipin Kumar. Graph partitioning for high performance scientific simulations. Army High Performance Computing Research Center, 2000.
[40] Daniel A. Spielman and Shang-Hua Teng. Spectral partitioning works: Planar graphs
and ﬁnite element meshes. In Proc. of the 37th Annual Symposium on Foundations of
Computer Science (FOCS), pages 96–105. IEEE Computer Society, 1996.
[41] Daniel A. Spielman and Shang-Hua Teng. Spectral partitioning works: Planar graphs and
ﬁnite element meshes. Linear Algebra and its Applications, 421(2):284–305, 2007.
[42] Chih-Chien Tu and Hsuanjen Cheng. Spectral methods for graph bisection problems.
Computers & operations research, 25(7):519–530, 1998.
[43] Chih-Chien Tu, Ce-Kuen Shieh, and Hsuanjen Cheng. Algorithms for graph partitioning
problems by means of eigenspace relaxations. European Journal of Operational Research,
123(1):86–104, 2000.
[44] René van Bevern, Andreas Emil Feldmann, Manuel Sorge, and Ondřej Suchỳ. On the
parameterized complexity of computing graph bisections. In Proc. International Workshop
on Graph-Theoretic Concepts in Computer Science (WG), pages 76–87. Springer, 2013.
[45] Lieven Vandenberghe and Stephen Boyd.
Semideﬁnite programming.
SIAM
Rev., 38(1):49–95, March 1996.
URL: http://dx.doi.org/10.1137/1038003,
doi:10.1137/1038003.
[46] Zhenyu Wu and Richard Leahy. An optimal graph theoretic approach to data clustering:
Theory and its application to image segmentation. IEEE transactions on pattern analysis
and machine intelligence, 15(11):1101–1113, 1993.

16

8 Proofs
Proof of Lemma 2.3
We know
sum(B opt ) − nλ(BSopt )
4
sum(B opt ) − 4 bw(G)
opt
λ(BS ) =
n
sum(A) + 4 bw(G) − 2|E| − 4 bw(G)
≥
=0
n

g(G, dopt ) = bw(G) =
⇔

B opt = A + diag(dopt )

(15)
X

dopt
≥ 4 bw(G) − 2|E|
i

i

Thus, we conclude that λ(BSopt ) ≥ 0.
We compute the value of the Rayleigh quotient of BSopt and the optimum bisection vector y:
y T BSopt y
y T P B opt P y
y T B opt y
=
=
kyk2
kyk2
n

y has mean zero

P
y T Ay + i dopt
y T (A + diag(dopt ))y
i
=
=
yi2 = 1 on the diagonal
n
n
P
We have y T Ay = i,j Aij yi yj . According to the deﬁnition Aij = 1 if there is an edge {i, j} ∈ E.
Edges with both vertices in the same part contribute (twice) by 1 to the sum. Cut edges
on the other hand contribute (twice) by −1. There are bw(G) cut edges. Hence, y T Ay =
sum(A) − 4 bw(G) and we get:
P
P
sum(A) − 4 bw(G) + i dopt
y T Ay + i dopt
sum(B opt ) − 4 bw(G) (15)
i
i
= λ(BSopt ).
=
=
n
n
n
Since the Rayleigh quotient of BSopt and y takes the value λ(BSopt ) and λ(BSopt ) ≥ 0, we
conclude that y is an eigenvector of BSopt corresponding to the eigenvalue λ(BSopt ).

Proof of Theorem 3.1
Due to Lemma 2.3, all optimum bisection vectors y are found in this subspace. We show even
more, namely that non-optimum bisection vectors y are not in this subspace. For contradiction,
assume y is eigenvector. Consider
P
y T BSopt y
y T Ay + i dopt
y T B opt y
y T (A + diag(dopt ))y
opt
i
=
=
=
.
λ(BS ) =
kyk
kyk
kyk
kyk

For a bisection vector y, the value y T Ay counts the number of cut edges. Since this has been
minimized, y has to be an optimal bisection.

Proof of Theorem 4.1
We start by proving the ﬁrst part, i.e. when we add an edge {u, v}. Let A and A′ denote the
∆
adjacency matrices of G and G′ , respectively. It holds A′ = A + A∆ with A∆
uv = Avu = 1 and
zero everywhere else. Since h(G) = bw(G), there exists a dopt with g(G, dopt ) = bw(G). For
G′ , we set d′ = dopt + d∆ with
(
−1 if i = u or i = v,
d∆
i =
0
else.

17

P opt
W.l.o.g. we restrict ourselves to solutions, with
= 4 bw(G) − 2|E| and hence have
i di
P
λ(BSopt ) = 0 where B opt = A + diag(dopt ). Since i d′i = 4 bw(G) − 2|E| − 2 = 4 bw(G) − 2|E ′ |,
we want to show that λ(BS′ ) = 0 holds, where B ′ = A′ + diag(d′ ). Since B ′ = A + A∆ +
diag(dopt + d∆ ) = B opt + A∆ + diag(d∆ ), we get
xT (B opt + A∆ + diag(d∆ ))x
kxk2
x∈S\{0}

λ(BS′ ) = max

xT B opt x + xT (A∆ + diag(d∆ ))x
kxk2
x∈S\{0}

= max

xT B opt x + 2xu xv − x2u − x2v
kxk2
x∈S\{0}

= max

xT B opt x − (xu − xv )2
kxk2
x∈S\{0}

= max

xT B opt x
= 0.
kxk2
x∈S\{0}
For the bisection vector of an minimal cut size, we have xu = xv = 1 or xu = xv = −1 and
thus the last inequality is equality. Hence, λ(BS′ ) = 0 and g(G′ , d′ ) = bw(G′ ). This completes
the proof for the ﬁrst part.
The proof for the second part is similar to the above one. Assume {u, v}, with u ∈ Y1
and v ∈ Y2 , is a removed edge from G. We deﬁne d∆ as we havePdone above and we let
′
∆
A′ = A + A∆ , with A∆
uv = Avu = −1 and zero everywhere else. Since
i di = 4 bw(G) − 2|E| −
′
′
2 = 4(bw(G) − 1) − 2(|E| − 1) = 4 bw(G ) − 2|E |, our aim is to show that λ(BS′ ) = 0 holds
with B ′ = A′ + diag(d′ ). Indeed we have:
≤ max

xT B opt x + xT (A∆ + diag(d∆ ))x
kxk2
x∈S\{0}

λ(BS′ ) = max

xT B opt x − 2xu xv − x2u − x2v
kxk2
x∈S\{0}

= max

xT B opt x − (xu + xv )2
kxk2
x∈S\{0}

= max

xT B opt x
= 0.
kxk2
x∈S\{0}
For the bisection vector of an optimal bisection size, we have xu = 1, xv = −1 or xu = −1, xv =
1 and hence the last inequality is equality. We can conclude
sum(B ′ ) − nλ(BS′ )
sum(B ′ ) − 0
4 bw(G) − 4
=
=
= bw(G) − 1.
g(G′ , d′ ) =
4
4
4
This completes the proof of the theorem.
≤ max

Proof of Lemma 5.1
The following fact is needed for the proof of Lemma 5.1. It has been observed independently
in [7].
Lemma 8.1. Let G be a graph with h(G) = bw(G) and let y be the bisection vector
of an
P opt
arbitrary optimum solution. Then for every dopt , with g(G, dopt ) = bw(G) and
d
=
i i
(y)
opt
(y)
(y)
4 bw(G) − 2|E|, there exists some α ∈ R such that d = d + α y.

18

Proof. The assumptions imply λ(BSopt ) = 0 with B opt = A + diag(dopt ). Next, due to a fact
stated in Lemma 2.3, y is an eigenvector of BSopt corresponding to the largest eigenvalue 0. We
get the following sequence of equivalent conditions:
BSopt y = 0y = (0, . . . , 0)T
⇔
⇔

P B opt P y = (0, . . . , 0)T
P B opt y = (0, . . . , 0)T

y has mean zero

Since P projects into the zero vector only vectors of the subspace spanned by the identity
vector, thus we can continue for some α ∈ R
⇔
⇔
⇔

⇔

B opt y = α(1, . . . , 1)T

(A + D opt )y = α(1, . . . , 1)T

D opt = diag(dopt )

Ay + D opt y = α(1, . . . , 1)T
D opt y = −Ay + α(1, . . . , 1)T

In the next step, we multiply the vectors in the equation with the diagonal matrix diag(y).
Since the yi ∈ {1, −1}, the multiplication is revertible and hence “⇔”.
⇔

⇔

diag(y)D opt y = − diag(y)Ay + α diag(y)(1, . . . , 1)T
dopt = − diag(y)Ay + αy

dopt = d(y) + αy
Def. 8
P
P (y)
This completes the proof. Note that i yi = 0 and i di = 4 bw(G) − 2|E|.
⇔

Proof of Lemma 5.1. Consider two optimum bisections with bisection vectors y and y ′ . (Note
that we consider y and −y as same bisection.) For contradiction, assume there are two different dopt
6= dopt
(up to a constant transition). Due to Lemma 8.1 we have that for every y
1
2
(y) + α y
can be expressed as dopt
and dopt
representing an optimum bisection values dopt
1
1 =d
2
1
opt
(y)
and d2 = d + α2 y. The diﬀerence is then
opt
dopt
1 − d2 = (α1 − α2 )y.

(y ) + β y ′ and dopt =
For y ′ representing an optimum bisection, we have analogously dopt
1
1 = d
2
′
d(y ) + β2 y ′ with diﬀerence
opt
′
dopt
1 − d2 = (β1 − β2 )y .
′

We conclude
(α1 − α2 )y = (β1 − β2 )y ′ .

Since y and y ′ are linearly independent, we conclude α1 = α2 and β1 = β2 . This means, if
there are two optimum bisections, then there is only one dopt and α is unique!

Proof of Theorem 5.2
Let G be a graph sampled from the subcritical phase and (V1 , V−1 ) be the planted bisection.
Coja-Oghlan [12] deﬁnes two sets of vertices:
Ni = {v ∈ Vi : e(v, Vi ) = e(v, V−i )}

Ni∗ = {v ∈ Ni : N (v) \ core(G) = ∅}

19

Let further (Y1 , Y−1 ) be an optimal bisection. Coja-Oghlan claims that, w.h.p., #(Yi ∩ Ni∗ ) ≥
µ/8
swap the parts), where µ = E(#N1 + #N−1 ) and µ ≥ n1−Θ(γ) with n(p′ − p) =
√ (eventually
np′ · γ ln n, γ = O(1) [13, page 122]. Then there are exp(Ω(µ)) many optimal bisections. On
the other hand, we will show that, assuming that Boppana works on G, the probability that
#(Yi ∩ Ni∗ ) ≥ 2 will tend to 0, which means that with w.h.p., Boppana will not work on G.
∗ . v and v
Consider any pair of vertices v1 ∈ Y1 ∩ N1∗ and v−1 ∈ Y−1 ∩ N−1
1
−1 are not
connected by an edge, since they have only neighbors in the core of G. Furthermore, they
both have balanced degree. Thus, we can apply Lemma 5.3 and conclude, that v1 and v−1
have the same neighbors. In direct consequence, all vertices in Yi ∩ Ni∗ , i ∈ {1, −1} have the
same neighbors and the same number of edges to each part as well. We denote this number
by k = e(v1 , V1 ).
In the following, we will consider sets of 4 vertices, while two are chosen from Y1 ∩ N1∗ and
∗ . By our assumption of #(Y ∩ N ∗ ) ≥ 2, we can choose at least one such
two from Y−1 ∩ N−1
i
i
set w.h.p.
Let us ﬁrst rule out two edge cases. In the ﬁrst case, the vertices have degree k = 0. Then
Boppana does not work due to Theorem 5.6. In the second case, the vertices have maximal
many edges, i.e. k = n/2 − 2 many edges to each part. W.h.p., a graph does not even have
two vertices in each part with k edges:
(n/2)2 (n/2 − 1)2 ′n/2−2 n/2−2 4
(p
p
) (1 − p)4 (1 − p′ )2 → 0
4
(k)

Thus, we have to consider 1 ≤ k ≤ n/2 − 2. Let Ci = {v ∈ Vi : e(v, Vi ) = e(v, V−i ) = k} be
the set of vertices with a balanced number of exactly k edges to each part. With the k from
(k)
above, we have Yi ∩ Ni∗ ⊆ Ci .
(k)
(k)
We want to estimate the expected number of 4-element sets {v1 , u1 , v−1 , u−1 } ⊆ C1 ∪ C−1
(k)

(k)

with v1 , u1 ∈ C1 and v−1 , u−1 ∈ C−1 , where all vertices have the same neighbors. Let us take
v1 as reference vertex and thus the k edges from v1 to V1 as well as k edges to V−1 are given.
Now we estimate the probability, that v−1 , u1 , u−1 have exactly the same neighbors. For each
vertex and each part, the k neighbors are chosen independently, since the four vertices are
not connected to each other. In both parts, there are n/2 − 2 possible neighbors. This makes

n/2−2
≥ n/2−2
= n/2 − 2 possibilities for the k edges in one part and only one of them
1
k
coincides with the edges of v1 . For 3 vertices to have the same neighbors as v1 in two parts
1
each, the probability is at most (n/2−2)
6 . The expected number of 4 vertices as described with
the same neighbors is therefore


(n/2)4
n/2 2
1
≤
→0
·
E(#4 − elem − set) ≤
(n/2 − 2)6
(n/2 − 2)6
2
This means, w.h.p. we will not ﬁnd any 4-element set. In consequence, #(Yi ∩ Ni∗ ) ≥ 2 may
not be true w.h.p.

Proof of Lemma 5.3
Let y be the bisection vector corresponding to the optimal bisection in the lemma. Let vi ∈ Yi ,
i ∈ {1, −1} be vertices as in the lemma, which fulﬁll e(vi , Yi ) = e(vi , Y−i ). We obtain the
bisection vector y ′ as vector corresponding to (Y1 \ {v1 } ∪ {v−1 }, Y−1 \ {v−1 } ∪ {v1 }). Due to
the balanced degree, this bisection is optimal as well.
Hence, we have two optimal bisections and from Lemma 5.1 we know, that the dopt is unique

20

′

and there are unique α(y) and α(y ) corresponding to y and y ′ , resp. It holds
′

′

d(y) + α(y) y = d(y ) + α(y ) y ′
′

′

⇔d(y) − d(y ) = α(y ) y ′ − α(y) y

Since v1 has balanced degree and is only connected to vertices, which are in the same part in
(y)
(y ′ )
y and y ′ , we have dv1 − dv1 = 0. Furthermore, yv1 = 1, yv′ 1 = −1. Thus we conclude by the
′
equation above, that −α(y ) − α(y) = 0.
Since y and y ′ are optimal bisections and e(vi , Yi ) = e(vi , Y−i ), we have
X
X
(y)
(y ′ )
di −
di = 0
i∈Y1 \{v1 }

because
P

(y)
i∈Y1 \{v1 } di

i∈Y1 \{v1 }

= bw(G) − e(v1 , Y−1 ) − 2 · |(Y1 \ {v1 }) × (Y1 \ {v1 }) ∩ E(G)| − e(v1 , Y1 )
P
(y ′ )
=
i∈Y1 \{v1 } di .

But we have also

X

(y)

di

i∈Y1 \{v1 }

(y ′ )

− di

′

′

= (n/2 − 1)(α(y ) − α(y) ) = −2α(y) (n/2 − 1)
(y)

(y ′ )

Thus, α(y) = α(y ) = 0. It follows di − di = 0, so that each vertex must have no edge to v1
and v−1 or must have an edge to both of them. Hence, the v1 and v−1 have exactly the same
neighbors.

Proof of Theorem 5.6
Let A be the adjacency matrix of G and


A
′

A =
0
0

0
0
0


0
0 
0

be the adjacency matrix of G′ , where we added two isolated vertices to G. Since h(G) = bw(G),
opt
opt
opt
there
P optexists a d , such that g(G, d ) = bw(G) and λ((A + d )S ) = 0. It then holds
= 4 bw(G) − 2|E|.
i di
h(G) − h(G′ )

g(G′ , d′ )
=g(G, dopt ) − max
′
d

sum(A′ ) + sum(d′ ) − (n + 2)λ(BS′ )
sum(A) + sum(dopt )
=
− max
d′
4
4
′
opt
sum(d ) − (n + 2)λ(BS′ )
sum(d )
=
− max
4
d′
4
T
opt
sum(z + (dopt , 0, 0)T ) − (n + 2)λ(BS′ )
sum(d )
− max
=
z
4
4
sum(z) − (n + 2)λ(BS′ )
= − max
z
4


n+2
sum(z)
′
= min
λ(BS ) −
z
4
4

21

′
= (A′ + diag(d′ ))S
BS

sum(A) = sum(A′ )

T
d′ = z + (dT
opt , 0, 0)

= min
z

= min
z



n+2
xT (A′ + diag(d′ ))x sum(z)
max
−
4 x∈S\{0}
kxk2
4
n+2
max
4 x∈S\{0}



xT (A′ + diag(z + (dTopt , 0, 0)T ))x
kxk2

!

sum(z)
−
4

!

We restrict ourselves two two kinds of vector xa = (x1 , . . . , xn , 0, 0)T with
xb = (1, . . . , 1, − n2 , − n2 ):
!
!
xT (A′ + diag(z + (dTopt , 0, 0)T ))x
sum(z)
n+2
max
−
≥ min
z
4 x∈{xa ,xb }
kxk2
4

Pn

i=1 xi

= 0 and

(16)

We want to show that this term is at least 4 bw(G)
. Therefore, we analyze the max-term
n2
separately and then show, for which d′ we have to choose which of the xa and xb .
Firstly, consider vector xa . Let z (n) denote the ﬁrst n components of vector z. Then
!
xTa (A′ + diag(z + (dTopt , 0, 0)T ))xa
max P
kxa k2
xa =(x1 ,...,xn ,0,0)T , n
i=1 xi =0
!
xT (A + diag(dopt ))x xT diag(z (n) )x
= Pnmax
+
kxk2
kxk2
i=1 xi =0
!
xT Bx xT diag(z (n) )x
+
= Pnmax
kxk2
kxk2
i=1 xi =0
We choose an optimal bisection vector y of G:
Pn
y T By y T diag(z (n) )y
zi
+
= i=1
≥
2
2
kyk
kyk
n

Lemma 2.3

(17)

Secondly, we consider xb = (1, . . . , 1, − n2 , − n2 )T :
xTb (A′ + diag(z + (dTopt , 0, 0)T ))xb
kxb k2
P opt
sum(A) + i di + xTb diag(z)xb
=
kxb k2
4 bw(G) + xTb diag(z)xb
=
kxb k2
Pn
4 bw(G)
i=1 zi + (zn+1 + zn+2 )


=
n +
(n + 2) 2
(n + 2) n2

X

dopt
= 4 bw(G) − 2|E|
i

i


n 2
2

We insert the result (17) for xa and (18) for xb into (16):
Pn
Pn
zi + (zn+1 + zn+2 )
4 bw(G)
n+2
i=1 zi
 + i=1

max
,
(16) ≥ min
n
z
4
n
(n + 2) 2
(n + 2) n2
We again simplify the terms separately for (17)
P
Pn+2
zi
n + 2 ni=1 zi
− i=1
4
n
4

22

(18)


n 2
2

!

sum(z)
−
4

!

=

(n + 2)

Pn

i=1 zi

−n

Pn

i=1 zi

− n(zn+1 + zn+2 )

4n
z
−
n(z
+
zn+2 )
i
n+1
i=1
=
4n
Pn
z
z
+ zn+2
1
i
n+1
= i=1 −
= δ
2n
4
2
and (18)
Pn+2
zi
n+2
(18) − i=1
4
4

Pn
Pn
n 2
zi zn+1 + zn+2
4 bw(G)
i=1 zi + (zn+1 + zn+2 ) 2
=
+
− i=1 −
2n
2n
4
4


X

n
4 bw(G)
n 1
1
1
=
zi +
+
−
−
(zn+1 + zn+2 )
2n
2n 4
8 4
2

Pn

δ=

Pn

i=1 zi

n

−

zn+1 + zn+2
2

i=1

n
2−nX

n−2
(zn+1 + zn+2 )
8
i=1
 Pn

zn+1 + zn+2
4 bw(G) 2 − n
i=1 zi
+
−
=
2n
4
n
2
2 bw(G) 2 − n
+
δ.
=
n
4
In both cases, the minimization over z could be reduced to a minimization over δ and we
conclude


1 2b 2 − n
′
h(G) − h(G ) ≥ (16) ≥ min max
δ,
+
δ .
δ
2 n
4

=

4 bw(G)
+
2n
4n

zi +

The ﬁrst term in the maximum is monotone increasing and the second one monotone decreasing
(for n ≥ 3). Hence, the minimum is at the intersection point of these two lines:
2 bw(G) 2 − n
1
δmin =
+
δmin
2
n
4
2−2+n
2 bw(G)
δmin =
4
n
2 bw(G)
n
δmin =
4
n
8 bw(G)
δmin =
n2
It follows
4 bw(G)
1
.
h(G) − h(G′ ) ≥ δmin =
2
n2

Proof of Proposition 6.1
To obtain an SDP formulation we start with Boppana’s function h(G) and transform it successively as follows:
sum(A + diag(d)) − nλ((A + diag(d))S )
h(G) = maxn
d∈R
4

23

J • A + 1T d − nλ(P (A + diag(d))P )
d∈R
4

J •A 1
+ maxn 1T d − nλ(P (A + diag(d))P )
=
4
4 d∈R


J •A 1
1T d
=
+ maxn −nλ(P (A + diag(d))P −
I)
4
4 d∈R
n


1T d
J •A n
− minn λ P (A + diag(d))P −
I
=
4
4 d∈R
n
J •A n
− minn λ(M (d)),
=
4
4 d∈R
= maxn

T

where M (d) = P (A + diag(d))P − 1n d I. Hence, we want to solve the following problem:
Minimize the largest eigenvalue of the matrix M (d) for d ∈ Rn . For this problem, [45] gives
the SDP formulation:
min z s.t. zI − M (d)  0,
T

with z ∈ R, d ∈ Rn . Inserting M (d) and then substituting z with z − 1n d , we get


1T d
min
z−
s.t. zI − P (A + diag(d))P  0.
z∈R,d∈Rn
n
It is easy to see that the constraint matrix above is equal to the constraint matrix of (11),
since P = I − Jn . This completes the proof that h(G) maximized by Boppana’s algorithm gives
the same value as the optimum solution of (11) because under the constraints we have
J •A 1
−
min (nz − 1T d).
h(G) =
4
4 z∈R,d∈Rn
To obtain the formulation for a dual program, consider the primal SDP in the form:
X
min n (nz − 1T d) s.t.
− P AP + zI −
di P Ii P  0,
z∈R,d∈R

i

where Ii denotes the matrix which has a single 1 in the ith row and the ith column and zero
everywhere else. The dual can be derived by using the rules (10). We obtain:
max (P AP ) • Y

Y ∈Rn×n

s.t. I • Y = n,

∀i : −P Ii P • Y = −1,

Y  0.

Thus, since P = I − Jn , we get the following formulation for the dual SDP:


sum(A)J
JA + AJ
max
+
•Y
A−
n
n2
Y ∈Rn×n
under the constraints:
X
yii = n,
i

1X
1 X
1X
yji −
yij + 2
∀i yii −
ykj = 1,
n
n
n
j

j

k,j

Y  0.

Here we can note that
P the second
P constraint is equal to (P Y P )ii = 1, for all i. Note
further that (AJ) • Y = i deg(i) j yij and an analogous holds for (JA) • Y . Hence, we can

24

reformulate the objective function as follows:


X
X
X
X
X
1
1
1
yij  .
deg(j)
yij −
deg(i)
yij + 2
max A • Y −
n
n
n
Y ∈Rn×n
j

i

i

i,j

j

This completes the proof.

Proof of Theorem 6.3
We start with the following fact:
P
Claim 8.2.
P Let X be a positive semidefinite matrix. Then the conditions (a) ∀i : j xij = 0
and (b) i,j xij = 0 are equivalent.
Proof. We show two directions. If (a) holds, it follows directly that (b) is true as well. We
proceed with proving of the second direction and assume, that (b) holds.
Each positive semideﬁnite matrix X can be represented as a Gram matrix, i.e. as matrix of
scalar products xij = hui , uj i of vectors ui . Thus, we have
X
X
X
X
X X
xij =
hui , uj i =
hui ,
uj i = h
ui ,
uj i = 0,
i,j

i,j

i

j

i

j

P

where we used condition (b). The scalar
P product of the vector i ui with itself is zero and we
conclude that it is the zero vector:
i ui = 0. Now we compute
X
X
X
xij =
hui , uj i = hui ,
uj i = hui , 0i = 0
j

j

j

which gives condition (a).

Now we ready to prove Theorem 6.3. For convenience we restate the primal SDP (13) as
follows:


X
|E| 1
− (A • Y )
s.t.
∀i yii = 1,
yij = 0, and Y  0,
(19)
hp (G) = min
Y
2
4
i,j

We show that for the following program

h′p (G) = max A • Y

(20)

Y

under the constraints:
∀i : yii = 1,
X
yij = 0,
i,j

we have h′p (G) = d(G), where recall, d(G)
|E|
1 ′
1
hp (G) = |E|
2 − 4 hp (G) = 2 − 4 d(G).

Y  0,

is the objective function of (12). Then we conclude

Consider an optimal solution matrix Y for the SDP. We show that Y is a solution to the
dual program (12) as well, with the value for the objective function equal to (20).P
Since yP
ii = 1, the ﬁrst constraint of (12) is fulﬁlled. Due to Claim 8.2 and since
i,j yij = 0,
we have j yij = 0 for all i. Hence, the second constraint of (12):
1X
1 X
1X
yji −
yij + 2
ykj = 1
∀i yii −
n
n
n
j

j

25

k,j

is fulﬁlled asPwell. In the
P objective function of (12), the second and third term are zero, since
(AJ) • Y = i deg(i) j yij = 0. Obviously, the fourth term is zero due to the constraints as
well. Hence, we obtain the same value as h′p (G).
For the other direction, consider an optimum solution
matrix Y of SDP (12). First we show
P
that the ﬁrst and second constraint of (12) imply i,j yij = 0:
1X
1 X
1X
second contraint of (12) for each i
yji −
yij + 2
ykj = 1
∀i yii −
n
n
n
j

⇒
⇒

X
i

1X
yji −
yii −
n
i,j
1X
n−
yji −
n
i,j

⇒

j

k,j

1X
n X
yij = n
yij + 2
n
n
i,j
i,j
1X
n X
yij + 2
yij = n
n
n
i,j
i,j
X
yij = 0.

sum all n constraints

use the first contraint of (12).

i,j

P

Next, due to Claim 8.2 we know that j yij = 0 for all i. Again from the second constraint,
of (12) we conclude that yii = 1. Hence, the constraints of the SDP (13) are fulﬁlled. Obviously,
the second, third and fourth term in the objective function of (12) are zero again and the
objective values of both SDPs are the same as well.

Lemma 8.3 and its Proof
Lemma 8.3 (Necessary for many edges). Let G = (V, E) be a graph and y an optimal bisection
vector of G. For i ∈ {+1, −1} let Ci = {u | yu = i ∧ ∃v : yv = −i ∧ {u, v} ∈ E} be
the set of vertices in part i located at the cut. If there exist non-empty C̃i ⊆ Ci with k =
min{|C̃+1 |, |C̃−1 |}, k + δ = max{|C̃+1 |, |C̃−1 |}, l = |V | − (k + δ), s.t.
7
4k 2
, 128
l})
• (3k < l ∧ δ = 0) or (4k < l ∧ δ < min{ l−4k
• 2|E(C̃+1 , C̃−1 )| ≥ |E(C̃+1 ∪ C̃−1 , V \ (C̃+1 ∪ C̃−1 ))|,
then h(G) < bw(G).
An illustration is found in Figure 2. The parameter δ allows for some unbalaced size of the
subsets.
δ

C̃+1

C̃−1

k

k

Figure 2: Forbidden graph structures as in Lemma 8.3.

Proof. For contradiction, we assume h(G) = bw(G). For the bisection vector y, we then have
dopt = d(y) + αy for some α ∈ R. Then λ(BS ) = 0 for B = A + diag(dopt ). We will contradict
this by choosing a vector x and then show that the Rayleigh quotient for x and BS is larger
than 0 (for any α). W. l. o. g. we assume |C̃+1 | ≥ |C̃−1 |. We choose

26

q



−1
xi = z


−βz
√

2kl+δl+2

2

if yi = +1 ∧ i 6∈ C̃+1 ,
if i ∈ C̃+1 ∪ C̃−1 ,
if yi = −1 ∧ i 6∈ C̃−1 ,

kl(k+δ)(l+δ)

. Note that for δ = 0, we have z = l/k > 3,
with β = δ+l/z
δ+l and z =
4k 2 +4δk−δl
β = 1/z < 1/3 and −βz = −1.
P
First we derive the z above by enforcing i xi = 0 and choosing β as above:
X
xi = l(−1) + (k + δ)z + kz + (δ + l)(−βz)
i

r

p

⇔

⇒

⇔

⇔

δz 2 + l
= −l + (k + δ)z + kz − (δ + l)
δ+l
p
!
2
= −l + (2k + δ)z − (δ + l)(δz + l) = 0

(δ + l)(δz 2 + l) = (2k + δ)z − l

(δ + l)(δz 2 + l) = ((2k + δ)z − l)2

δ2 z 2 + δl + δlz 2 + l2 = (2k + δ)2 z 2 + l2 − 2(2k + δ)lz

δ2 z 2 + δl + δlz 2 = 4k2 z 2 + δ2 z 2 + 4kδz 2 − 4klz − 2δlz

0 = (4k2 + 4kδ − δl)z 2 + (−4kl − 2δl)z − δl
p
2kl + δl ± (2kl + δl)2 + δl(4k2 + 4kδ − δl)
z=
4k2 + 4kδ − δl
p
2kl + δl ± 4(kl)2 + 4klδl + δl(4k2 + 4kδ)
z=
4k2 + 4kδ − δl
p
2kl + δl ± 2 kl(kl + δl + δ(k + δ))
z=
4k2 + 4kδ − δl
p
2kl + δl ± 2 kl(k + δ)(l + δ)
z=
4k2 + 4kδ − δl

⇔

⇔
⇔
⇔
⇔

We take the larger z-solution with the +.
We show that by our choice of β, the sum of squares for both parts is the same:
X
X
x2i −
x2i = (l(−1)2 + (k + δ)z 2 ) − (kz 2 + (δ + l)(−βz)2 )
i:yi =+1

i:yi =−1

δz 2 + l
δ+l
= l + (k + δ)z 2 − kz 2 − (δz 2 + l) = 0

= l + (k + δ)z 2 − kz 2 − (δ + l)
Thus, α will have no eﬀect:
xT Bx
xT BS x
=
kxk2
kxk2
=

xT (A + diag(d(y) + αy)x
kxk2

27

=
=

xT (A + diag(d(y) ))x + xT (αy)x
kxk2
xT (A + diag(d(y) ))x
kxk2

xT (αy)x = α

X

yi x2i = 0

i

(21)
2

4k
7
From now we consider the case 4k < l and δ < min{ l−4k
, 128
l}. Next we show z > 4. From
2

4k
, we get for the denominator of z that 4k2 + 4kδ − δl > 0. For the enumerator, we
δ < l−4k
have:
p
p
2kl + δl + 2 kl(k + δ)(l + δ) = 2kl + 5δl + 2 kl(k + δ)(l + δ) − 4δl
p
> 8k2 + 20δk + 4 k2 (k + δ)(4k + δ) − 4δl Assumption 4k < l
√
= 8k(k + δ) + 12δk + 4 k2 4k2 − 4δl

> 16k(k + δ) − 4δl

= 4(4k(k + δ) − δl)

4 times denominator of z

Since the enumerator is more than 4 times larger then the denominator and both are positive,
7
l follows further, that β < 1/3:
we conclude z > 4. From δ < 128
 2
δ + l/z 2
1
1
2
β =
≤ =
δ+l
9
3
⇔

⇔
⇐
⇔

9(δ + l/z 2 ) ≤ δ + l
9l
8δ ≤ l − 2
z
9l
8δ ≤ l −
16
7
l
δ≤
16 · 8

z>4

Now we want to show that (21) is larger than zero. For this we decompose B = A + diag(d(y)
P
(y)
into B = e∈E B e and analyze xT B e x for each edge e separately. Note that di is for vertex
i the number of neighbors in the other part minus the number of neighbors in the same part.
e = 1, if e = {i, j} is a cut edge and B e = B e = −1, if
For the decomposition, we set Biie = Bjj
ii
jj
e is a inner edge. Further, Bij = Bji = 1.
If e = {i, j} is a cut edge, we have xT B e x = 2xi xj + x2i + x2j = (xi + xj )2 . Thus, cut edges
always contribute positive. We only consider the edges E(C̃+1 , C̃−1 ). Since xi = xj = z, they
contribute 4z 2 each.
If e = {i, j} is a inner edge, we have xT B e x = 2xi xj − x2i − x2j . For inner edges in V \ (C̃+1 ∪
C̃−1 ), xi = xj and the contribution is 0. The same holds for inner edges in C̃+1 and C̃−1 . Thus,
we only have to consider the edges E(C̃+1 ∪ C̃−1 , V \ (C̃+1 ∪ C̃−1 )). One vertex is z, the other
−1 or −βz < −1. Thus, the contribution is −2z − 1 − z 2 or −2βz 2 − β 2 z 2 − z 2 = −(3β + 1)z 2 .
Since 0 < β < 1/3, both are larger than −2z 2 .
We conclude:
xT Bx > |E(C̃+1 , C̃−1 )| · 4z 2 + |E(C̃+1 ∪ C̃−1 , V \ (C̃+1 ∪ C̃−1 ))| · (−2z 2 )

By the assumption in the Lemma, this is greater or equal to zero.

28

