Self-referential instances of the dominating set problem are irreducible

Authors: Guangyan Zhou

We study the algorithmic decidability of the domination number in the Erdos-Renyi random graph model $G(n,p)$. We show that for a carefully chosen edge probability $p=p(n)$, the domination problem exhibits a strong irreducible property. Specifically, for any constant $0