Abstract: New Spectral Lower Bounds on the Bisection Width of Graphs
Sergei L. Bezrukov,
Robert Elsaesser,
Burkhard Monien ,
Robert Preis , and
Jean-Pierre Tillich
The communication overhead is a major bottleneck for
the execution of a process graph on a parallel computer system.
In the case of two processors, the minimization of
the communication can be modeled by the graph bisection problem.
The spectral lower bound of \lambda_2|V|/4 for the
bisection width of a graph is well-known.
The bisection width is equal to the spectral lower bound
iff all vertices are incident to \lambda_2/2 cut edges
in every optimal bisection.
We discuss the case for which this fact is not satisfied
and present a new method to get tighter lower bounds on the
bisection width.
This method makes use of the level structure defined by the bisection.
Under certain conditions we get a lower bound depending
on \lambda_2^\beta|V| with 1/2 < \beta < 1.
We also present examples of graphs for which our new bounds are tight
up to a constant factor.
As a by-product, we derive new lower bounds for the bisection widths of
3- and 4-regular graphs.
We use them to establish tighter lower bounds for the
bisection width of 3- and 4-regular Ramanujan graphs.