Local minimum structures of graph-coloring problems for stochastic constraint satisfaction algorithms

Many stochastic search algorithms developed to solve large-scale constraint satisfaction problems in a practical time have the drawback of becoming stuck in locally minimal solutions which are not acceptable as solutions. We analyze a stochastic search algorithm from the viewpoint of local constraint structures of local minima. Using the graph-coloring problem with three colors, we studied the local graph structures around which concurrent conflicts arise. We present a key constraint structure, an LM pair; which may make up a local minimum, clarifying the mechanism of how conflicted coloring in an LM pair hinders stepwise refinement of hill-climbing. Experimental results show that LM pairs are strongly correlated with the search efficiency of the stochastic search algorithm