MOMENTS OF INERTIA AND GRAPH SEPARATORS

Graphs that arise from the finite element or finite difference methods often include geometric information such as the coordinates of the no des of the graph. The geometric separator algorithm of Miller, Teng, T hurston, and Vavasis uses some of the available geometric information to find small node separators of graphs. The algorithm utilizes a rand om sampling technique based on the uniform distribution to find a good separator. We show that sampling from an elliptic distribution based on the inertia matrix of the graph can significantly improve the quali ty of the separator. More generally, given a cost function f on the un it d-sphere U-d, we can define an elliptic distribution based on the s econd moments of f. The expectation of f with respect to the elliptic distribution is less than or equal to the expectation with respect to the uniform distribution, with equality only in degenerate cases. We a lso demonstrate experimentally that the benefit gained by the use of t he additional geometric information is significant. Some previous algo rithms have used the moments of inertia heuristically, and suffer from extremely poor worst case performance. This is the first result, to o ur knowledge, that incorporates the moments of inertia into a provably good strategy.