A Note on the Asymptotics and Computational Complexity of Graph Distinguishability

Source abstract

A graph $G$ is said to be $d$-distinguishable if there is a $d$-coloring of $G$ which no non-trivial automorphism preserves. That is, $\exists \chi: G \rightarrow \{1, \ldots, d\},$ $$\forall \phi \in \mathrm{Aut}(G) \setminus \{\mathbf{id}\}, \exists v, \chi(v) \neq \chi(\phi(v)).$$ It was conjectured that if $|G| > |\mathrm{Aut}(G)|$ and the $\mathrm{Aut}(G)$ action on $G$ has no singleton orbits, then $G$ is 2-distinguishable. We give an example where this fails. We partially repair the conjecture by showing that when "enough motion occurs," the distinguishing number does indeed decay. Specifically, defining $${\mathrm{m} }(G) = \min_{{\phi \in \mathrm{Aut}(G)} \atop {\phi \neq \mathbf{id}}} |\{v \in G \;:\;\phi(v) \neq v\}|,$$ we show that when ${\mathrm{m}}(G) > 2\log_2 |\mathrm{Aut}(G)|$, $G$ is 2-distinguishable. In general, we show that if ${\mathrm{m}}(G)\ln d > 2\ln |\mathrm{Aut}(G)|$ then $G$ is $d$-distinguishable. There has been considerable interest in the computational complexity of the $d$-distinguishability problem. Specifically, there has been much musing on the computational complexity of the language $$\{(G, d)\; : \; G \text{ is $d$-distinguishable}\}.$$ We show that this language lies in AM $\subset \Sigma_2^P \cap \Pi_2^P$. We use this to conclude that if Dist is $\mathbf{coNP}$-hard then the polynomial hierarchy collapses.