\documentclass[12pt,reqno,letterpaper]{article}
\usepackage{times,amsmath,amsfonts,amsthm,mathptm}
% This is LaTeX 2e code, using the AMSTeX packages. It should compile
% to 7 pages.
\newcommand{\aut}{\text{Aut}}
\newcommand{\cclass}[1]{\textsc{#1}}
\newcommand{\lang}[1]{\textsc{#1}}
\newcommand{\id}{\textbf{id}}
\newcommand{\setst}[2]{\left\{#1\::\:#2\right\}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
% EJC Page lengths
\textheight 9in
\textwidth 6in
\topmargin -0.2in
\oddsidemargin 0.1in
\evensidemargin 0.1in
\title{A Note on the Asymptotics and Computational Complexity of Graph
Distinguishability}
\author{Alexander Russell\\ {\tt acr@cs.utexas.edu}\\ Department of
Computer Science\\ University of
Texas at Austin\\
Austin, TX 78712 \and Ravi Sundaram\\ {\tt koods@delta-global.com}\\
Delta Global Trading\\
141 Tremont Street, 12th Floor\\
Boston, MA 02111}
\date{Submitted: February 2, 1998; Accepted: March 24, 1998}
\begin{document}
\bibliographystyle{plain} \maketitle
% EJC Headings
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 5 (1998),
\#R23\hfill}
\thispagestyle{empty}
\begin{abstract}
A graph $G$ is said to be \emph{$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 \aut(G) \setminus \{\id\}, \exists v, \chi(v)
\neq \chi(\phi(v)).
$$
It was conjectured that if $|G| > |\aut(G)|$ and the $\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
$$
{\mathfrak m}(G) = \min_{\substack{\phi \in \aut(G) \\ \phi \neq
\id}} |\setst{v \in G}{\phi(v) \neq v}|,
$$
we show that when ${\mathfrak m}(G) > 2\log_2 |\aut(G)|$, $G$ is
indeed 2-distinguishable. In general, we show that if $
{\mathfrak m}(G)\ln d > 2\ln |\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
$$
\setst{(G, d)}{G \text{ is $d$-distinguishable}}.
$$
We show that this language lies in $\cclass{AM} \subset
\Sigma_2^P \cap \Pi_2^P$. We use this to conclude that if
$\lang{Dist}$ is $\cclass{coNP}$-hard then the polynomial
hierarchy collapses.
\vspace{12pt}
\noindent AMS Classification: Primary: 05C25; Secondary: 68Q15.
\end{abstract}
\section{Introduction}
An undirected graph $G$ is \emph{$d$-distinguishable} if there is a
$d$ coloring of $G$ which no non-trivial automorphism preserves.
Formally, we write $\exists \chi: G \rightarrow \{1,\ldots,d\},$
$$
\forall \phi \in \aut(G) \setminus \{\id\}, \exists v, \chi(v) \neq
\chi(\phi(v)),
$$
where $\aut(G)$ denotes the collection of automorphisms of the
graph $G$ and $\id$ denotes the identity map. One says that such a
coloring ``destroys the symmetries'' of $G$. Every graph $G$ is then
$|G|$-distinguishable and a graph is 1-distinguishable exactly when it
is {\em rigid}, i.e. $|\aut(G)| = 1$. The smallest $d$ for which $G$
is $d$-distinguishable is dubbed the \emph{distinguishing number} of
$G$, denoted ${\mathfrak d}(G)$. An instantiation of this machinery,
mentioned in \cite{AlbertsonC:Symmetry}, is the problem of coloring keys on a (circular)
key chain so that one can uniquely identify each key. (In this case,
one is interested in the distinguishing number of the dihedral
groups.)
A paper of Albertson and Collins \cite{AlbertsonC:Symmetry} gracefully
develops the theory of distinguishability in several directions. They
conjectured that if $|G| > |\aut(G)|$ and the action of $\aut(G)$ on
$G$ has no singleton orbits, then ${\mathfrak d}(G) = 2$. Though there are
graphs for which this fails\footnote{Select a large rigid graph $H$
and let $G_H$ be the graph formed by the disjoint union of $K_3$ and
3 copies of $H$. Then $\aut(G_H) = S_3 \times S_3$, $G_H$ has no one
cycles, ${\mathfrak d}(G_H) = 3$, and $|G_H|$ can be arbitrarily
large.}, the idea that \emph{few colors suffice if every
automorphism moves many vertices} can be substantiated.
Specifically, for an automorphism $\phi \in \aut(G)$, define the
\emph{motion} of $\phi$ as
$$
{\mathfrak m}(\phi) = |\setst{v \in G}{\phi(v) \neq v}|.
$$
The \emph{motion} of a graph $G$ is then $${\mathfrak m}(G) =
\min_{\substack {\phi \in \aut(G) \\ \phi \neq \id}}
{\mathfrak m}(\phi).$$
We show that when ${\mathfrak m}(G) > 2\log_2
|\aut(G)|$, $G$ is 2-distinguishable. More generally, when ${\mathfrak
m}(G) \ln d > 2\ln |\aut(G)|$, $G$ is $d$-distinguishable.
Another natural question is that of the computational complexity of
the graph distinguishability problem (see the discussion in
\cite{AlbertsonC:Symmetry}). Specifically, one would like to place
the language
$$
\lang{Dist} = \setst{(G, d)}{{\mathfrak d}(G) \leq d},
$$
as low in the natural hierarchy of complexity classes as possible.
There is no obvious $\cclass{NP}$ algorithm for this language; the
only immediate conclusion is that $\lang{DIST} \in \Sigma_2^P$. We
show that $\lang{Dist} \in \cclass{AM} \subset \Pi_2^P \cap
\Sigma_2^P$.
\section{Graphs with Large Motion can be Distinguished with Few
Colors}
We now return to the first theorem advertised in the introduction, namely
\begin{theorem}\label{th:motion}
If ${\mathfrak m}(G) > 2\log_2 |\aut(G)|$ then $G$ is
2-distinguishable.
\end{theorem}
Anticipating the proof, we define the \emph{cycle norm} as follows:
decomposing an automorphism $\phi$ into a product of disjoint cycles
$$\phi = (v_{11}v_{12}\ldots v_{1l_1})(v_{21}\ldots
v_{2l_2})\ldots(v_{k1}\ldots v_{kl_k}),
$$
the \emph{cycle norm} of $\phi$ is the quantity
$$
{\mathfrak c}(\phi) = \sum_{i=1}^k (l_i - 1).
$$
The cycle norm is relevant to graph distinguishability in the
following sense. Suppose that a graph $G$ is randomly two-colored by
independently assigning each vertex a color uniformly {from}
$\set{\text{red},\text{black}}$. Then the probability that every cycle
of an automorphism $\phi$ is monochromatic is exactly $2^{-{\mathfrak
c}(\phi)}$. When this event occurs, the automorphism $\phi$
preserves the coloring so chosen.
For convenience, the cycle norm of a graph $G$ is defined
$$
{\mathfrak c}(G) = \min_{\substack{\phi \in \aut(G)\\ \phi \neq \id}}
{\mathfrak c}(\phi).
$$
Notice that for any automorphism, ${\mathfrak c}(\phi) \geq {\mathfrak
m}(\phi)/2$. Of course, then ${\mathfrak c}(G) \geq {\mathfrak
m}(G)/2$. With this observation, Theorem~\ref{th:motion} above is an
easy consequence of the following theorem:
\begin{theorem}
If ${\mathfrak c}(G) \ln d > \ln |\aut(G)|$ then $G$ is
$d$-distinguishable.
\end{theorem}
\begin{proof}
We study the behavior of a random $d$-coloring of $G$, the
probability distribution given by selecting the color of each vertex
independently and uniformly in the set $\{1, \ldots, d\}$. Fix an
automorphism $\phi \neq \id$ and consider the bad event that the random
coloring $\chi$ is in fact preserved by $\phi$: an easy calculation
shows that
$$
\Pr_\chi[\forall v, \chi(v) = \chi(\phi(v))] =
(\frac{1}{d})^{{\mathfrak c}(\phi)} \leq (\frac{1}{d})^{{\mathfrak
c}(G)}.
$$
Collecting together these bad events, we have
$$
\Pr_\chi[\exists \phi \neq \id, \forall v, \chi(v) = \chi(\phi(v))]
\leq |\aut(G)|(\frac{1}{d})^{{\mathfrak c}(G)}.
$$
The hypothesis of the theorem is exactly that this quantity is
less than one, in which case there exists a coloring $\chi$ for
which $\forall \phi \neq \id, \exists v, \chi(v) \neq
\chi(\phi(v))$, as desired.
\end{proof}
For a delightful survey of the probabilistic method, of which the above
is an example, see \cite{AlonS:Probabilistic}.
It is interesting to notice that the above theorem is actually tight
in the case of the dihedral groups $D_3, D_4, \ldots$ mentioned in the
introduction (and in \cite{AlbertsonC:Symmetry}). (The answers are
${\mathfrak d}(D_3) = 3, {\mathfrak d}(D_4) = 4, {\mathfrak d}(D_5) =
2, {\mathfrak d}(D_6) = 2, \ldots$.)
\section{$\lang{Dist} \in \cclass{AM}$}
Though we will discuss the definition of $\cclass{AM}$ in some detail,
for a general introduction to complexity theory and detailed
discussions of the polynomial time hierarchy and $\cclass{AM}$, we
refer the reader to \cite{KoblerST:Graph} and
\cite{BDG:StructuralI,BDG:StructuralII}.
The polynomial time hierarchy is the ``polynomial time bounded
variant'' of the Kleene hierarchy of recursive function theory. One
defines $\Sigma^P_0 = \Pi^P_0 = \cclass{P}$, and, in general, $L \in
\Sigma_k^P$ if there is a polynomial $p$ and $D \in \Pi_{k-1}^P$
for which
$$
L = \setst{w}{\exists \pi, |\pi| \leq p(|w|), \langle w, \pi
\rangle \in D}.
$$
Finally, define the class $\Pi_k^P$ to consist of all languages $L$
for which $\overline{L} \in \Sigma_k^P$. Above, the notation
$\langle\cdot,\cdot\rangle$ refers to some canonical pairing function.
With these definitions, $\cclass{NP} = \Sigma_1^P$, $\cclass{coNP} =
\Pi_1^P$, and the classes $\Sigma_k^P$ and $\Pi_k^P$ form a neat
hierarchy containing $\cclass{P}$ and lying inside $\cclass{PSPACE}$.
Considering the quantifier alternation in the definition of the
distinguishability problem, it is not surprising that $\lang{Dist} \in
\Sigma_2^P$, as an easy argument shows. Our goal here is to show that
$\lang{Dist} \in \cclass{AM} \subset \Sigma_2^P \cap \Pi_2^P$.
$\cclass{AM}$ is the class of languages for which there are
\emph{Arthur--Merlin} games (see \cite{BabaiM:Arthur-Merlin}).
Intuitively, an Arthur--Merlin game for a language $L$ is played by
two players, \emph{Arthur}, equipped with a random coin and only modest
(polynomial-time bounded) computing power and \emph{Merlin}, who is
computationally unbounded. Both Arthur and Merlin are supplied with a
word $x$, and the goal of the game is for Arthur to determine if $x
\in L$. Arthur, based on his coin flips, may ask Merlin a constant
number of questions, and, having heard Merlin's answers, must then
decide to \emph{accept} that $x \in L$ or \emph{reject} this
statement. Of course, a natural question for Arthur to ask is, ``$x
\in L$?'' Unfortunately, rather than being the trustworthy advisor we
might hope, Merlin actually has a vested interest in seeing that
Arthur accept the predicate. An Arthur--Merlin game, then, is a
strategy for Arthur to follow in his questioning of Merlin so that:
\begin{itemize}
\item When $x \in L$, regardless of Arthur's coin tosses (which may
determine the questions he asks of Merlin under this strategy),
Merlin can answer satisfactorily, convincing Arthur to accept that
$x \in L$.
\item When $x \not\in L$, regardless of way in which Merlin answers,
the discussion ends with Arthur rejecting that $x \in L$ a constant
fraction of the time. (The probability distribution is taken over
Arthur's coin tosses.)
\end{itemize}
The number of questions which Arthur is allowed to ask may depend on
the language, but not the specific input. Furthermore, the entire
conversation must have length polynomial in the length of the
input. In the above model, Arthur's coin flips are \emph{public}--
Merlin can see them.
Hopefully, it is clear from this vague definition that every language
in $\cclass{NP}$ has an (easy) Arthur-Merlin game. We will show that
there is an Arthur-Merlin game for the language $\lang{Dist}$. First,
a formal definition:
\begin{definition}
For a function $M: \{0,1\}^* \rightarrow \{0,1\}^p$, and random
variables $X_1, X_2, \ldots, X_R \in \{0,1\}^p$, let
$$
M_X = (M(X_1), M(\langle X_1, X_2\rangle), \ldots, M(\langle X_1,
\ldots, X_R\rangle)).
$$
$\cclass{AM}$ consists of those languages $L$
for which there exists a constant $R$, a polynomial $p$, and a
polynomial time bounded Turing machine $A$ so that:
\begin{itemize}
\item $x \in L \Rightarrow \exists M:\{0,1\}^* \rightarrow
\{0,1\}^{p(|x|)},$
$$
\Pr_{\{X_i\}}[A(x,X_1,\ldots,X_R,M_X) \text{ accepts}] = 1,
$$
where the $X_i$ are independent uniform random variables on
$\{0,1\}^p$.
\item $x \not\in L \Rightarrow \forall M:\{0,1\}^* \rightarrow
\{0,1\}^{p(|x|)}$,
$$
\Pr_{\{X_i\}}[A(x,X_1,\ldots,X_R,M_X) \text{ accepts}] \leq \frac{1}{2},
$$
where the $X_i$ are independent uniform random variables on
$\{0,1\}^p$.
\end{itemize}
\end{definition}
We start by showing that the language of rigid graphs is in
$\cclass{AM}$. Let
$$
\lang{Rigid} = \setst{G}{|\aut(G)| = 1}.
$$
\begin{theorem}
$\lang{Rigid} \in \cclass{AM}$
\end{theorem}
\begin{proof}
The proof is an easy adaptation of the result of
\cite{GMR:Knowledge,GS:Private} that the language
$$
\lang{NGI} = \setst{(G_1,G_2)}{G_1 \not\simeq G_2}
$$
is in $AM$. In the formulation of $\cclass{AM}$ given above,
Merlin observes Arthur's coin tosses. This scenario is aptly dubbed
the ``public'' coin model. In fact, in the formalization above,
Arthur's questions to Merlin are exactly his coin tosses (the random
variables $X_i$ in the above definition). Since Arthur is
deterministic aside from his coin tossing, any question he might
wish to have answered can be anticipated and duly answered by
Merlin. In the alternative model, involving ``private'' coin tosses,
Arthur's questions may not completely reveal the coins he has tossed
so far. It is rather remarkable that the two models are in fact
equivalent \cite{GS:Private}. We shall allow ourselves the
flexibility of a private coin in our constructions. Our goal is to
show that $\lang{Rigid} \in \cclass{AM}$. Given input $G = ([n],E)$,
consider the following protocol:
\begin{enumerate}
\item Arthur generates a random permutation $\sigma \in S_n$, and sends
Merlin the graph $G_\sigma = ([n], E_\sigma)$, where
$$
E_\sigma = \setst{(\sigma(u),\sigma(v))}{(u,v) \in E}.
$$
\item Arthur expects Merlin to respond with an element of $S_n$. Given
any other response, Arthur rejects. Upon receiving $\tau \in
S_n$. Arthur accepts exactly if $\tau = \sigma$.
\end{enumerate}
Notice that when $G$ is rigid, there is a unique isomorphism between
$G$ and $G_\sigma$, so that Merlin does indeed have a strategy which
always convinces Arthur to accept. Suppose instead that $G$ is
non-rigid so that $|\aut(G)| > 1$. In this case, there are exactly
$|\aut(G)|$ isomorphisms between $G$ and $G_\sigma$ and, furthermore,
conditioned on Arthur asking the question $G_\sigma$ to Merlin, each of
these isomorphisms is equally like to be the one used by Arthur to
construct $G_\sigma$. Hence no strategy of Merlin can induce accepting
behavior in Arthur for more than a $|\aut(G)|^{-1} \leq \frac{1}{2}$
fraction of Arthur's coin tosses.
\end{proof}
\begin{theorem}
$\lang{Dist} \in \cclass{AM}$.
\end{theorem}
\begin{proof}
Let $(G = ([n],E), k)$ be the common input, and consider the
following protocol:
\begin{enumerate}
\item Arthur expects Merlin to send him $\chi:G \rightarrow [k]$, a
$k$-coloring of $G$. On any other message, Arthur rejects.
\item Arthur builds a new graph $G'$ follows. Starting with $G$,
Arthur adds for every vertex $v$ of $G$ a fresh $(n +
\chi(v))$-clique, called $K_v$. Each vertex $v$, aside from
maintaining its old connections inside $G$ is attached to each
vertex of $K_v$. An easy argument shows that the isomorphisms of
$G'$ are in one-to-one correspondence with isomorphisms of $G$
which fix $\chi$. Specifically, if $\chi$ destroyed all of the
symmetries of $G$, $G'$ is rigid. Arthur now uses the protocol
described above for $\lang{Rigid}$.
\end{enumerate}
It is now easy to check that this protocol satisfies the
requirements in the definition of $\cclass{AM}$.
\end{proof}
Based on constructions like those of
\cite{stoc:Sipser83a,Lautemann:BPP,RS:Symmetric}, one has $\cclass{AM}
\subset \Sigma_2^P \cap \Pi_2^P$, completing the claim in the
introduction.
One naturally wonders at the relationship of $\lang{Dist}$ to more
familiar classes such as $\cclass{NP}$ and $\cclass{coNP}$. In this
direction, applying the machinery of \cite{BHZ:Does}, we can argue that it is
unlikely that $\lang{Dist}$ is $\cclass{coNP}$-hard. Specifically,
{from} \cite{BHZ:Does}, we have the following theorem:
\begin{theorem}
If $\cclass{coNP} \subset \cclass{AM}$, then the polynomial
hierarchy collapses to $\Sigma_2^P$, specifically $\Sigma_k^P
\subset \Sigma_2^P$ for all $k$.
\end{theorem}
In our case, were $\lang{Dist}$ to be $\cclass{coNP}$-complete,
$\cclass{coNP} \subset \cclass{AM}$, and we could apply the above
theorem. Complementing, this shows that the language
$$
\lang{Robust} = \setst{(G,k)}{\forall \chi:G \rightarrow [k], \exists
\gamma \in \aut(G) \setminus \{\id\}, \gamma \text{ preserves }\chi}
$$
is unlikely to be $\cclass{NP}$ hard.
\section{An Open Problem}
An outstanding open question is whether the language $\lang{Dist}$ is
in fact $\cclass{NP}$-hard.
\section{Acknowledgments}
We thank Karen Collins for originally introducing us to the problem
during her engaging talk at M.I.T. and several helpful discussions.
\begin{thebibliography}{10}
\bibitem{AlbertsonC:Symmetry}
Michael~O. Albertson and Karen~L. Collins.
\newblock Symmetry breaking in graphs.
\newblock {\em Electronic Journal of Combinatorics}, 3, 1996.
\newblock R18.
\bibitem{AlonS:Probabilistic}
Noga Alon and Joel~H. Spencer.
\newblock {\em The Probabilistic Method}.
\newblock John Wiley \& Sons, Inc., 1992.
\bibitem{BabaiM:Arthur-Merlin}
L\'{a}szl\'{o} Babai and Shlomo Moran.
\newblock Arthur-merlin games: a randomized proof system, and a hierarchy of
complexity classes.
\newblock {\em Journal of Computer and System Sciences}, 36(2):254--276, 1988.
\bibitem{BDG:StructuralI}
{Jos\'{e}}~Luis {Balc\'{a}zar}, Josep {D\'{i}az}, and Joaquim {Gabarr\'{o}}.
\newblock {\em Structural Complexity I}, volume~11 of {\em {EATCS} Monographs
on Computer Science}.
\newblock Springer-Verlag, Berlin, 1988.
\bibitem{BDG:StructuralII}
{Jos\'{e}}~Luis {Balc\'{a}zar}, Josep {D\'{i}az}, and Joaquim {Gabarr\'{o}}.
\newblock {\em Structural Complexity {II}}, volume~22 of {\em {EATCS}
Monographs on Computer Science}.
\newblock Springer-Verlag, Berlin, 1990.
\bibitem{BHZ:Does}
Ravi Boppana, Johan {H\aa stad}, and Stathis Zachos.
\newblock Does {co-NP} have short interactive proofs?
\newblock {\em Information Processing Letters}, 25:127--132, 1981.
\bibitem{GMR:Knowledge}
Shafi Goldwasser, Silvio Micali, and Charles Rackoff.
\newblock The knowledge complexity of interactive proof systems.
\newblock {\em {SIAM} Journal of Computing}, 18(1):186--208, February 1989.
\bibitem{GS:Private}
Shafi Goldwasser and Michael Sipser.
\newblock Private coins versus public coins in interactive proof systems.
\newblock {\em Advances in Computing Research}, 5:73--90, 1989.
\bibitem{KoblerST:Graph}
Johannes {K\"{o}bler}, Uwe {Sch\"{o}ning}, and Jacobo Tor\'{a}n.
\newblock {\em The Graph Isomorphism Problem: Its Structural Complexity}.
\newblock Progress in Theoretical Computer Science. {Birkh\"{a}user}, Boston,
1993.
\bibitem{Lautemann:BPP}
Clemens~Lautemann.
\newblock {BPP} and the polynomial hierarchy.
\newblock {\em Information Processing Letters}, 17:215--217, 1983.
\bibitem{RS:Symmetric}
Alexander Russell and Ravi Sundaram.
\newblock Symmetric alternation captures {BPP}.
\newblock {\em Computational Complexity}, 6, 1996.
\bibitem{stoc:Sipser83a}
Michael Sipser.
\newblock A complexity theoretic approach to randomness.
\newblock In {\em Proceedings of the Fifteenth Annual ACM Symposium on Theory
of Computing}, pages 330--335, Boston, Massachusetts, 25--27 April 1983.
\end{thebibliography}
\end{document}