HOW GOOD IS RECURSIVE BISECTION

The most commonly used p-way partitioning method is recursive bisectio n (RB). It first divides a graph or a mesh into two equal-sized pieces , by a ''good'' bisection algorithm, and then recursively divides the two pieces. Ideally, we would like to use an optimal bisection algorit hm. Because the optimal bisection problem that partitions a graph into two equal-sized subgraphs to minimize the number of edges cut is NP-c omplete, practical RE algorithms use more efficient heuristics in plac e of an optimal bisection algorithm. Most such heuristics are designed to find the best possible bisection within allowed time. We show that the RE method, even when an optimal bisection algorithm is assumed, m ay produce a pa ay partition that is very far way from the optimal one . Our negative result is complemented by two positive ones: first we s how that for some important classes of graphs that occur in practical applications, such as well-shaped finite-element and finite-difference meshes, RE is within a constant factor of the optimal one ''almost al ways.'' Second, we show that if the balance condition is relaxed so th at each block in the p-way partition is bounded by 2n/p, where n is th e number of vertices of the graph, then a modified RE finds an approxi mately balanced p-way partition whose cost is within an O(log p) facto r of the cost of the optimal p-way partition.