Questions tagged [automorphism]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
16
votes
2answers
862 views

Relationship between symmetry and computational intractability?

The $k$-fixed point free automorphism problem asks for a graph automorphism which moves at least $k(n)$ nodes. The problem is $NP$-complete if $k(n)=n^c$ for any $c$>0. However, If $k(n)=O(\log n)$ ...
11
votes
1answer
566 views

what are known bounds on complexity of nontrivial graph automorphism

Given any simple undirected graph G, it is nontrivial to determine if G has nontrivial (non-identity) automorphisms. But what are results on upper/lower bounds of this decision problem?
7
votes
1answer
280 views

Complexity of counting poset automorphisms

A (finite) poset $P = (X, <)$, or partially ordered set, is a (finite) set $X$ equipped with a transitive antisymmetric relation $<$; it can be equivalently seen as a DAG $G = (X, E)$ that is ...