Optimizing partitions of percolating graphs

The partitioning of random graphs is investigated numerically using \simulated annealing " and \extremal optimization". While generally in an NP-hard problem, it is shown that the optimization of the graph partitions is particularly dicult for sparse graphs with average connectivities near the percolation threshold. At this threshold, the relative error of \simulated annealing " is found to diverge in the thermodynamic limit. On the other hand, \extremal optimization", a new general purpose method based on self-organized criticality, produces near-optimal partitions with bounded error at any low connectivity at a comparable computational cost. c © 1999 Elsevier Science B.V. All rights reserved