New spectral lower bounds on the bisection width of graphs

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 using the graph bisection problem. The spectral lower bound of lambda(2)\V\/4 for the bisection width of a graph is widely known. The bisection width is equal to lambda(2)\V\/4 iff all vertices are incident to lambda(2)/2 cut edges in every optimal bisection. We present a new method of obtaining tighter lower bounds on the bisection width. This method makes use of the level structure defined by the bisection. We define some global expansion proper-ties and we show that the spectral lower bound increases with this global expansion. Under certain conditions we obtain a lower bound depending on lambda(2)(beta)\V\ with 1/2 less than or equal to 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 Ramanujan graphs. (C) 2004 Elsevier B.V. All rights reserved.