13
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Oct 9 '10 at 21:35
  • 2
    $\begingroup$ 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). $\endgroup$
    – Tsuyoshi Ito
    Oct 9 '10 at 21:41
  • $\begingroup$ 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? $\endgroup$
    – Niel de Beaudrap
    Oct 9 '10 at 22:47
  • 1
    $\begingroup$ One issue here is that we need to choose a set $S$ for which membership testing is in NP. $\endgroup$
    – Emil
    Oct 9 '10 at 23:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – Douglas S. Stones
    Oct 10 '10 at 4:56
15
$\begingroup$

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...

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$
    – Jukka Suomela
    Oct 10 '10 at 8:56
  • 5
    $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Oct 12 '10 at 19:31
  • 1
    $\begingroup$ @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...) $\endgroup$
    – Jukka Suomela
    Oct 12 '10 at 20:24
  • $\begingroup$ @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). $\endgroup$
    – Joshua Grochow
    Oct 12 '10 at 20:39
  • $\begingroup$ @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? $\endgroup$
    – Jukka Suomela
    Oct 13 '10 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.