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.