On the Threshold
Where the Bugs Are
Over the past year the concept of survey propagation has been further refined and embodied in a series of computer programs by Mézard and Zecchina and a group of coworkers. Contributors include Alfredo Braunstein, Silvio Franz, Michele Leone, Andrea Montanari, Roberto Mulet, Andrea Pagnani, Federico Ricci-Tersenghi and Martin Weigt.
To solve a three-coloring problem on a graph of size n, the algorithm first finds the vertex that is most highly biased toward one color or another, and permanently sets the color of that vertex accordingly. Then the algorithm is invoked recursively on the remaining graph of n–1 vertices, so that another vertex color is fixed. Obviously this process has to terminate after no more than n repetitions. In practice it usually stops sooner, when all the signals propagating through the network have become messages of indifference, putting no constraints on neighboring nodes. At this point survey propagation has nothing more to offer, but the graph that remains has been reduced to a trivial case for other methods.
As with other algorithms for NP-complete problems, survey propagation comes with no guarantees, and it does sometimes fail. The process of deciding which vertex to fix next is not infallible, and when a wrong choice is made, there may be no later opportunity to recover from it. (Adding some form of backtracking or randomized restarting might alleviate this problem.) In its present form the algorithm is also strictly one-sided: It can usually color a colorable graph, but it cannot prove a graph to be uncolorable.
Nevertheless, the algorithm has already had some impressive successes, particularly in the hard-to-solve region near the phase transition. The version for satisfiability has solved problems with 8 million variables. The graph-coloring program handles graphs of a million vertices. Both of these numbers are two orders of magnitude beyond what is routine practice for other methods.
Graph coloring and satisfiability are not just toy problems for theorists. They are at the core of various practical tasks in scheduling, in the engineering of silicon circuits and in optimizing computer programs. Having an algorithm capable of solving much larger instances could open up still more applications.
Ironically, although survey propagation works well on enormous problems, it sometimes stalls on much smaller instances, such as random graphs with only a few hundred vertices. This is not a pressing practical concern, since other methods work well in this size range, but it's annoying, and there's the worry that the same failures might show up in larger nonrandom graphs. The cause of these small-graph failures is not yet clear. It may have to do with an abundance of densely nested loops and other structures in the graphs. Then again, it may be just another bug in the universe.
© Brian Hayes