Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search
Abstract
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.
Cite
Text
Culberson et al. "Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search." International Joint Conference on Artificial Intelligence, 2005.Markdown
[Culberson et al. "Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/culberson2005ijcai-phase/)BibTeX
@inproceedings{culberson2005ijcai-phase,
title = {{Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search}},
author = {Culberson, Joseph C. and Gao, Yong and Anton, Calin},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2005},
pages = {78-83},
url = {https://mlanthology.org/ijcai/2005/culberson2005ijcai-phase/}
}