A randomized algorithm for finding a near-maximum clique and its experimental evaluations

The so-called Maximum Clique Problem is one of the most famous NP-complete problems which are difficult to find a solution. Given a graph of n nodes, the authors present here an O(n³)-time randomized algorithm RaCLIQUE for finding a near-maximum clique. While the basic idea of the algorithm comes from Boltzmann machines, it employes no simulated annealing at all and hence is simple to control its execution. The authors have confirmed in experiments for several random and nonrandom graphs with up to 400 nodes that almost optimum solutions can be found very efficiently compared with the other conventional algorithms. [In Japanese.]