<p>Take any language $L$ (that consists of binary strings). Construct the set $S$ of graphs as follows:</p>

<ul>
<li>For each string $x \in L$ with $|x| = n$, we have the graph $G_x = (V_x,E_x)$ in $S$, with the set of nodes $V_x = \{1,2,...,3n\}$ and the following edges: if bit $i$ of $x$ is $0$, then the nodes $3i-2$ and $3i-1$ are adjacent, otherwise $3i-2$ and $3i$ are adjacent. There are no other edges.</li>
</ul>

<p>Now let $p$ be a permutation of $\{1,2,...,3n\}$. Assume that $p$ is an automorphism of some graph in $S$. That is, $p$ is an automorphism of $G_y$ for some $y \in L$. Let $i \in \{1,2,...,n\}$. Let us consider the following two cases:</p>

<ul>
<li>$p(3i-2) = 3i-1$, $p(3i-1) = 3i-2$, $p(3i) = 3i$. Then we must have bit $i$ of $y$ equal to $0$.</li>
<li>$p(3i-2) = 3i$, $p(3i-1) = 3i-1$, $p(3i) = 3i-2$. Then we must have bit $i$ of $y$ equal to $1$.</li>
</ul>

<p>Hence if we can solve the question "is a given $p$ automorphism of some $G \in S$", we can also solve the question "is a given string $y$ in $L$". Moreover, if we can do the former in, say, polynomial time in $|p|$, we can do the latter in polynomial time in $|y|$ as well.</p>

<p>Now you can just let $L$ be your favourite NP-hard problem. Or the halting problem...</p>

CC BY-SA 2.5
2010-10-10T08:56:25.177Z
And to actually answer the original question: Let $L$ be an NP-complete problem, and you will have an $S$ such that the automorphism problem is NP-complete. The certificate for a "yes" answer is a $G_y \in S$ such that $p$ is the automorphism of $G_y$, plus the certificate for $y \in L$.
Jukka Suomela
CC BY-SA 2.5
2010-10-12T19:31:17.113Z
@Jukka: One way to make the question closer to the original motivation of Latin square graphs is to require that the set $S$ of graphs be closed under isomorphism. This is also quite a natural restriction. The set $S$ you construct from an arbitrary language $L$ is not closed under isomorphism and, in this very specific sense, is a bit unnatural.  I do not see how to modify your construction to satisfy this constraint, but I think it would be very interesting if it could be done.
Joshua Grochow
CC BY-SA 2.5
2010-10-12T20:24:35.623Z
@Joshua: I think it is possible to modify the construction, for example as follows: both the graphs and the permutations that we use in the queries consist of *disjoint cycles*. In more detail, $G_x$ contains a cycle of length $2i+a+1$ iff bit $i$ of $x$ is equal to $a$. Similarly, to determine whether $y \in L$, construct a permutation $p$ that contains a cycle of length $2i+a+1$ iff bit $i$ of $y$ is equal to $a$. (I might have overlooked some details, but I think the basic idea should work...)
Jukka Suomela
CC BY-SA 2.5
2010-10-12T20:39:42.060Z
@Jukka: Nice. I believe the new construction works as written (assuming we only allow $p \in S_n$ to act on graphs with exactly $n$ vertices, and not graphs with more than $n$ vertices).
Joshua Grochow
CC BY-SA 2.5
2010-10-13T09:15:39.873Z
@Joshua: I guess the possibility of applying $p \in S_n$ to graphs with more than $n$ nodes does not matter, if we assume that the language $L$ uses a prefix-free code?
Jukka Suomela
CC BY-SA 2.5
2010-10-13T17:11:12.857Z
@Jukka: I think that's right.  And if we express CNF formulae using a prefix-free code, then we get a prefix-free language isomorphic to SAT.
Joshua Grochow
CC BY-SA 2.5
2010-10-10T08:40:56.320Z
2010-10-10T08:40:56.320Z
Jukka Suomela
<p>Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S.</p>
<blockquote>
<p>Instance: A permutation p in P.</p>
<p>Question: Does there exist a graph g in S that admits the automorphism p?</p>
</blockquote>
<p>Is this problem NP-complete for some sets S?</p>
<p>It would be easy to check that a graph admits the permutation p (i.e. certificate).  Moreover, it's easy to find examples of S where the problem is not NP-complete, such as S being the set of complete graphs, whence the answer is always yes.</p>
<p>Note: I'm not really interested in what type of graphs they are; if you like they can be non-simple, directed, coloured, etc.</p>
<p>ADDENDUM:  The problem I'm currently looking at is classifying which isotopisms are autotopisms of Latin squares (which can also be interpreted as a special type of graph automorphism).</p>
<p>Given a Latin square L(i,j) we can construct a graph in the following way:</p>
<ul>
<li>The vertex set is the set of cells (i,j) in the matrix and</li>
<li>There is an edge between distinct (i,j) and (i',j') whenever i=i' or j=j' or L(i,j)=L(i',j').</li>
</ul>
<p>Such a graph is called a <em>Latin square graph</em> (see e.g. this article by Bailey and Cameron <a href="http://designtheory.org/library/encyc/topics/lsee.pdf" rel="noreferrer">http://designtheory.org/library/encyc/topics/lsee.pdf</a>).  We can interpret an autotopism of a Latin square as an automorphism of the Latin square graph.  So let S be the set of Latin square graphs formed from the Latin squares of order n.  So the question I'm interested in is:</p>
<blockquote>
<p>Given a permutation p, is p an automorphism of one (or more) of the graphs in S?</p>
</blockquote>
<p>My feeling is that it is a difficult question to answer in general -- I'm currently writing a 30+ page paper on the matter (with 2 co-authors).  Actually most of the time it is easy (most of the time it's &quot;no&quot;), but there are some difficult cases.</p>
<p>So I'm interested in finding decision problems that would be related to &quot;symmetry classification&quot;.  They don't really need to be related to Latin squares, I'm just hoping to use these techniques to answer the question for Latin squares.</p>

CC BY-SA 2.5
2010-10-09T21:35:30.067Z
I am not sure if I understand the problem correctly.  Can you give an example of S and P (and the group action of P on S)?  An example which makes the problem nontrivial (neither all-yes or all-no) will help to understand the problem.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T21:41:00.863Z
In the example of complete graphs, what I do not understand is how a permutation on k points acts on the complete graph on n points, where k≠n (especially if k>n).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T22:47:20.830Z
I managed to fool myself into thinking that I understood the problem, but I've now decided that I don't. Does the group of permutations S act on the graphs in the family P, or only *potentially* act on the graphs in the family P?
Niel de Beaudrap
CC BY-SA 2.5
2010-10-09T22:59:04.313Z
@Niel: Nitpicking: you are writing S and P swapped.  In the question, P is a permutation group and S is a set of graphs.  I understand that it can be confusing if you consider the symmetric group S_n and view S as a graph property, which is often written P.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-09T23:24:53.100Z
One issue here is that we need to choose a set $S$ for which membership testing is in NP.
Emil
CC BY-SA 2.5
2010-10-09T23:48:21.580Z
@Tsuyoshi: thank you for the edification and your understanding, but I merely wrote too quickly.
Niel de Beaudrap
CC BY-SA 2.5
2010-10-10T04:56:11.430Z
I've added a bit more background in the answer.  Actually, in general, I don't really care about whether or not the group acts on S, just as long as we can answer "is this permutation an automorphism of that graph?"  In the case of Latin squares, we can interpret it as a group action.
Douglas S. Stones
<cc.complexity-theory><graph-theory><np-hardness><automorphism>
Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?
Douglas S. Stones
# Is "Is a permutation p an automorphism of a graph in my set?" NP-complete?

(Asked by: username_0 on 2010-10-09)

Suppose we have a set S of graphs (finite graphs, but an infinite number of them) and a group P of permutations that acts on S.

> Instance: A permutation p in P.
>
> Question: Does there exist a graph g in S that admits the automorphism p?

Is this problem NP-complete for some sets S?

It would be easy to check that a graph admits the permutation p (i.e. certificate). Moreover, it's easy to find examples of S where the problem is not NP-complete, such as S being the set of complete graphs, whence the answer is always yes.

Note: I'm not really interested in what type of graphs they are; if you like they can be non-simple, directed, coloured, etc.

ADDENDUM: The problem I'm currently looking at is classifying which isotopisms are autotopisms of Latin squares (which can also be interpreted as a special type of graph automorphism).

Given a Latin square L(i,j) we can construct a graph in the following way:

* The vertex set is the set of cells (i,j) in the matrix and
* There is an edge between distinct (i,j) and (i',j') whenever i=i' or j=j' or L(i,j)=L(i',j').

Such a graph is called a *Latin square graph* (see e.g. this article by Bailey and Cameron <http://designtheory.org/library/encyc/topics/lsee.pdf>). We can interpret an autotopism of a Latin square as an automorphism of the Latin square graph. So let S be the set of Latin square graphs formed from the Latin squares of order n. So the question I'm interested in is:

> Given a permutation p, is p an automorphism of one (or more) of the graphs in S?

My feeling is that it is a difficult question to answer in general -- I'm currently writing a 30+ page paper on the matter (with 2 co-authors). Actually most of the time it is easy (most of the time it's "no"), but there are some difficult cases.

So I'm interested in finding decision problems that would be related to "symmetry classification". They don't really need to be related to Latin squares, I'm just hoping to use these techniques to answer the question for Latin squares.

**Tags:** cc.complexity-theory, graph-theory, np-hardness, automorphism

> **Comments:**
> **username_1**: I am not sure if I understand the problem correctly.  Can you give an example of S and P (and the group action of P on S)?  An example which makes the problem nontrivial (neither all-yes or all-no) will help to understand the problem.  
> **username_1**: In the example of complete graphs, what I do not understand is how a permutation on k points acts on the complete graph on n points, where k≠n (especially if k>n).  
> **username_2**: I managed to fool myself into thinking that I understood the problem, but I've now decided that I don't. Does the group of permutations S act on the graphs in the family P, or only *potentially* act on the graphs in the family P?  
> **username_1**: @Niel: Nitpicking: you are writing S and P swapped.  In the question, P is a permutation group and S is a set of graphs.  I understand that it can be confusing if you consider the symmetric group S_n and view S as a graph property, which is often written P.  
> **username_3**: One issue here is that we need to choose a set $S$ for which membership testing is in NP.  
> **username_2**: @Tsuyoshi: thank you for the edification and your understanding, but I merely wrote too quickly.  
> **username_0**: I've added a bit more background in the answer.  Actually, in general, I don't really care about whether or not the group acts on S, just as long as we can answer "is this permutation an automorphism of that graph?"  In the case of Latin squares, we can interpret it as a group action.  

---

## 1 answers

### Answer by username_4 on 2010-10-10. Score: 15 | Accepted answer

Take any language $L$ (that consists of binary strings). Construct the set $S$ of graphs as follows:

* For each string $x \in L$ with $|x| = n$, we have the graph $G\_x = (V\_x,E\_x)$ in $S$, with the set of nodes $V\_x = \{1,2,...,3n\}$ and the following edges: if bit $i$ of $x$ is $0$, then the nodes $3i-2$ and $3i-1$ are adjacent, otherwise $3i-2$ and $3i$ are adjacent. There are no other edges.

Now let $p$ be a permutation of $\{1,2,...,3n\}$. Assume that $p$ is an automorphism of some graph in $S$. That is, $p$ is an automorphism of $G\_y$ for some $y \in L$. Let $i \in \{1,2,...,n\}$. Let us consider the following two cases:

* $p(3i-2) = 3i-1$, $p(3i-1) = 3i-2$, $p(3i) = 3i$. Then we must have bit $i$ of $y$ equal to $0$.
* $p(3i-2) = 3i$, $p(3i-1) = 3i-1$, $p(3i) = 3i-2$. Then we must have bit $i$ of $y$ equal to $1$.

Hence if we can solve the question "is a given $p$ automorphism of some $G \in S$", we can also solve the question "is a given string $y$ in $L$". Moreover, if we can do the former in, say, polynomial time in $|p|$, we can do the latter in polynomial time in $|y|$ as well.

Now you can just let $L$ be your favourite NP-hard problem. Or the halting problem...

> **Comments:**
> **username_4**: And to actually answer the original question: Let $L$ be an NP-complete problem, and you will have an $S$ such that the automorphism problem is NP-complete. The certificate for a "yes" answer is a $G_y \in S$ such that $p$ is the automorphism of $G_y$, plus the certificate for $y \in L$.  
> **username_5**: @Jukka: One way to make the question closer to the original motivation of Latin square graphs is to require that the set $S$ of graphs be closed under isomorphism. This is also quite a natural restriction. The set $S$ you construct from an arbitrary language $L$ is not closed under isomorphism and, in this very specific sense, is a bit unnatural.  I do not see how to modify your construction to satisfy this constraint, but I think it would be very interesting if it could be done.  
> **username_4**: @Joshua: I think it is possible to modify the construction, for example as follows: both the graphs and the permutations that we use in the queries consist of *disjoint cycles*. In more detail, $G_x$ contains a cycle of length $2i+a+1$ iff bit $i$ of $x$ is equal to $a$. Similarly, to determine whether $y \in L$, construct a permutation $p$ that contains a cycle of length $2i+a+1$ iff bit $i$ of $y$ is equal to $a$. (I might have overlooked some details, but I think the basic idea should work...)  
> **username_5**: @Jukka: Nice. I believe the new construction works as written (assuming we only allow $p \in S_n$ to act on graphs with exactly $n$ vertices, and not graphs with more than $n$ vertices).  
> **username_4**: @Joshua: I guess the possibility of applying $p \in S_n$ to graphs with more than $n$ nodes does not matter, if we assume that the language $L$ uses a prefix-free code?  
> **username_5**: @Jukka: I think that's right.  And if we express CNF formulae using a prefix-free code, then we get a prefix-free language isomorphic to SAT.  

---

