Anton: Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search

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 thresh-old 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 “uni-formly hard ” with a tiny runtime variance on neg-ative 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.