Self-referential instances of the dominating set problem are irreducible

Referee: [Local symmetry mapping paragraph] The local symmetry mapping (described after the statement of the main theorem) is asserted to produce instances that are indistinguishable under G(n,p) after altering only a constant number of edges. However, the manuscript does not supply an explicit functional form for p(n) nor a calculation showing that the likelihood ratio for each such edge flip is 1 + o(1). When p(n) → 0 or p(n) → 1, even a single edge flip multiplies the probability by a factor Θ(1/p) or Θ(1/(1-p)), which is unbounded; without a concrete p(n) that keeps this factor bounded for the specific flips used, the total-variation distance between the original and mapped distributions may be Ω(1), undermining the claim that every n^c-sized induced subgraph leaves the global answer undetermined.

Authors: We agree that an explicit choice of p(n) must be supplied. In the revision we will set p(n) = 1 - e^{-1} (a constant), which places the threshold for the existence of a dominating set of size k = ln n exactly at the point where the expectation transitions. For this fixed p the likelihood ratio incurred by adding or removing any single edge is bounded by the n-independent constant max(e-1, 1/(e-1)) ≈ 1.718. Because the local symmetry mapping alters only a constant number of edges, the overall Radon-Nikodym derivative between the original and mapped measures is therefore bounded by a fixed constant C. We will insert a short calculation establishing this bound. In addition, the probability that any fixed induced subgraph on n^c vertices contains one of the flipped edges is O(n^{2c-2}) = o(1). Consequently the distributions of all n^c-sized induced subgraphs under the two measures differ by o(1) in total variation, which is the quantity needed for the irreducibility argument. revision: yes

Referee: [Proof of indistinguishability] The abstract states that the mapping 'produces indistinguishable random graph instances which require exhaustive search,' yet no quantitative bound is given on the total-variation distance or on the probability that the mapped graph remains in the support of G(n,p). A concrete lemma establishing that the two distributions are o(1)-close in total variation (or that the Radon–Nikodym derivative is 1 + o(1) uniformly over the relevant flips) is needed to make the irreducibility argument load-bearing.

Authors: We will add a new lemma (placed immediately after the definition of the local symmetry mapping) that quantifies the indistinguishability of local views. The lemma states that, for any set S of size at most n^c, the total-variation distance between the law of the induced subgraph G[S] and the law of the mapped graph's induced subgraph is o(1). The proof proceeds by observing that the flipped edges lie outside S with probability 1-o(1) and that the bounded Radon-Nikodym derivative (established in the preceding paragraph) multiplies probabilities by at most C; the resulting local TV distance is therefore o(1). We note that the global measures need not be o(1)-close in total variation; a bounded derivative suffices once the o(1) probability of observing the flipped edges is taken into account. The mapped graph remains in the support of G(n,p) with probability 1, since the mapping only toggles existing or non-existing edges. revision: yes