ON THE QUALITY OF SPECTRAL SEPARATORS

Computing graph separators is an important step in many graph algorith ms. A popular technique for finding separators involves spectral metho ds. However, there has not been much prior analysis of the quality of the separators produced by this technique; instead it is usually claim ed that spectral methods ''work well in practice.'' We present an init ial attempt at such an analysis. In particular, we consider two popula r spectral separator algorithms and provide counterexamples showing th at these algorithms perform poorly on certain graphs. We also consider a generalized definition of spectral methods that allows the use of s ome specified number of the eigenvectors corresponding to the smallest eigenvalues of the Laplacian matrix of a graph, and we show that if s uch algorithms use a constant number of eigenvectors, then there are g raphs for which they do no better than using only the second smallest eigenvector. Furthermore, using the second smallest eigenvector of the se graphs produces partitions that are poor with respect to bounds on the gap between the isoperimetric number and the cut quotient of the s pectral separator. Even if a generalized spectral algorithm uses n(eps ilon) for 0 < epsilon < 1/4 eigenvectors, there exist graphs for which the algorithm fails to find a separator with a cut quotient within n( 1/4-epsilon)-1 of the isoperimetric number. We also introduce some fac ts about the structure of eigenvectors of certain types of Laplacian a nd symmetric matrices; these facts provide the basis for the analysis of the counterexamples. Finally, we discuss some developments in spect ral partitioning that have occurred since these results first appeared .