Self-referential instances of the dominating set problem are irreducible
Abstract
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
Fields of Study & Subjects
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Limits and Structures in Graph Theory
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 11 February 2026
- Language
- EN
- Document type
- Preprint