Phase transitions of dominating clique problem and their implications to heuristics in satisfiability search
Joseph C. Culberson, Yong Chao Gao, Cǎlin Anton · International Joint Conference on Artificial Intelligence · 2005
We study a monotone NP decision problem, the dominating clique problem, whose phase transition occurs at a very dense stage of the random graph evolution process. We establish the exact threshold of the phase transition and propose an efficient search algorithm that runs in super-polynomial time with high probability. Our empirical studies reveal two even more intriguing phenomena in its typical-case complexity: (1) the problem is uniformly hard with a tiny runtime variance on negative instances. (2) Our algorithm and its CNF-tailored implementation, outperform several SAT solvers by a huge margin on dominating cliques and some other SAT problems with similar structures.