Reweighted Spectral Partitioning Works: Bounds for Special Graph Classes

Spectral partitioning is a method that can be used to compute small sparse cuts or small edge-separators in a wide variety of graph classes, by computing the second-smallest eigenvalue (and eigenvector) of the Laplacian matrix. Upper bounds on this eigenvalue for certain graph classes imply that the method obtains small edge-separators for these classes, usually with a sub-optimal dependence on the maximum degree. In this work, we show that a related method, called reweighted spectral partitioning, guarantees near-optimal sparse vertex-cuts and vertex-separators in a wide variety of graph classes. In many cases, this involves little-to-no necessary dependence on maximum degree. We also obtain a new proof of the planar separator theorem, a strengthened eigenvalue bound for bounded-genus graphs, and a refined form of the recent Cheeger-style inequality for vertex expansion via a specialized dimension-reduction step.