Optimizing partitions of percolating graphs

The partitioning of random graphs is investigated numerically using "simula ted annealing" and "extremal optimization". While generally in an NP-hard p roblem, it is shown that the optimization of the graph partitions is partic ularly difficult for sparse graphs with average connectivities near the per colation threshold. At this threshold, the relative error of "simulated ann ealing" is found to diverge in the thermodynamic limit. On the other hand, "extremal optimization", a new general purpose method based on self-organiz ed criticality, produces near-optimal partitions with bounded error at any low connectivity at a comparable computational cost. (C) 1999 Elsevier Scie nce B.V. All rights reserved.