Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 78-82.
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 CNFtailored implementation, outperform several SAT solvers by a huge margin on dominating cliques and some other SAT problems with similar structures.
@inproceedings{ijcai2005p160,
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 = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {78--82},
year = {2005},
url = {https://ijcai.org/proceedings/2005/160},
}
TY - CPAPER TI - Phase Transitions of Dominating Clique Problem and Their Implications to Heuristics in Satisfiability Search AU - Culberson, Joseph C. AU - Gao, Yong AU - Anton, Calin T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 78 EP - 82 UR - https://ijcai.org/proceedings/2005/160 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
