Self-referential instances of the dominating set problem are irreducible

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 do…