MK seminar of 10/20/04

Spectral methods (i.e., methods that use the eigenvalues and eigenvectors of a matrix representation of a graph) are widely used to compute graph separators. Typically, the Laplacian matrix is used; the Laplacian B of a graph G on n vertices is the n * n matrix with the degrees of the vertices of G on the diagonal and entry b[i,j] = -1 if E(i,j) else 0. The eigenvector (u2) corresponding to the second smallest eigenvalue of B [x is an eigenvector of B iff xB = cx for some constant c which is the eigenvalue coresponding to x] is computed and the vertices are partitioned according to their values in u2. The goal is to compute a small separator which has as few edges crossing it given the partitions are roughly similar.
The measure being optimized here is min(over S \subset of V) { e(S,V-S)/min{|S|,|V - S|} }, which is exactly the sparsest cut. In timothee's paper he was optimizing min(over S \subset of V) { e(S,V-S)( 1/|S| + 1/|V -S| ) }. these are very similar since in timothee's cost function the term which does not have |S| < n/2 is less than a constant and is hence not the deciding factor in the choice of the cut (at least it does not make optimal worse by factor 2).
A simple bisection using spectral partitioning has performance as poor as Omega(n) in case of half cut ladder graphs. Using this cut quotient and the isperimetric number we have another algorithm. We present a class of graphs for which the spectral cut's cut quotient is removed from the min ratio cut by a large factor.