Computational Complexity
Constructing the automorphism group is at least as difficult (in terms of its computational complexity) as solving the graph isomorphism problem, determining whether two given graphs correspond vertex-for-vertex and edge-for-edge. For, G and H are isomorphic if and only if the disconnected graph formed by the disjoint union of graphs G and H has an automorphism that swaps the two components.
The graph automorphism problem is the problem of testing whether a graph has a nontrivial automorphism. It belongs to the class NP of computational complexity. Similar to the graph isomorphism problem, it is unknown whether it has a polynomial time algorithm or it is NP-complete. There is a polynomial time algorithm for solving the graph automorphism problem for graphs where vertex degrees are bounded by a constant (Luks 1982). It is known that the graph automorphism problem is polynomial-time many-one reducible to the graph isomorphism problem, but the converse reduction is unknown.
Read more about this topic: Graph Automorphism
Famous quotes containing the word complexity:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)