Graph separator theorems and sparse Gaussian elimination
John R. Gilbert · 1980
This thesis reports an investigation of some divide-and-conquer algorithms on graphs. A graph problem can often be solved by cutting the graph into two or more pieces of roughly equal size, solving the problem on the pieces, and combining the partial results to get a solution to the original problem. We begin by considering the conditions under which a graph can be divided by removing a small set of vertices. Lipton and Tarjan have shown that a planar graph can be split in half by removing a set of vertices whose size is proportional to the square root of the size of the graph; we say that such graphs have square root separators. Other separator theorems are known for trees, hypercubes, and various graphs that have been suggested as interconnection patterns for parallel processors. Most of these separator theorems generalize to graphs with weighted vertices. We show that if a graph and its subgraphs have square root separators, and the vertices have two independent sets of nonnegative weights, then the graph has a square root separator that cuts one kind of weight exactly in half and the other kind in half to within any specified tolerance. We use this result to prove that, in a graph with square root separators and vertices of average weight one, a fragment of any specified weight can be isolated with a separator whose size is proportional to the square root of the fragment's weight. Second, we analyze an algorithm for a combinatorial problem that arises in numerical analysis. A large system of linear equations whose coefficients are nearly all zeroes can be solved by Gaussian elimination, but in the process the zeroes often become nonzero. Nonzeroes must be stored and operated upon explicitly, so it is advantageous to order the computations in a way that creates relatively few nonzeroes. The generalized nested dissection algorithm, due to Lipton, Rose, and Tarjan, efficiently provides a good ordering for systems that can be represented as graphs having square root separators. We analyze a simpler variant of this algorithm, and show that it provides good orderings at least for systems that arise from two-dimensional finite difference and finite element problems. The chapter closes with a preliminary exploration of the interplay between continuous and discrete methods in an algorithm that preserves zeroes and has good numerical behaviour. The detailed analysis of a divide-and-conquer algorithm usually involves solving a recurrence relation. The third chapter of the thesis examines one such recurrence, which relates the difficulty of separating a graph into small pieces to the number of edges that the graph can have. The final chapter describes open problems and possible extensions of the thesis work.