1998 | OriginalPaper | Buchkapitel
On the Complexity of Counting the Number of Vertices Moved by Graph Automorphisms
verfasst von : Antoni Lozano, Vijay Raghavan
Erschienen in: Foundations of Software Technology and Theoretical Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We consider the problem of deciding whether a given graph G has an automorphism which moves at least k vertices (where k is a function of ∣ V(G) ∣), a question originally posed by Lubiw (1981). Here we show that this problem is equivalent to the one of deciding whether a graph has a nontrivial automorphism, for k ∈ O(logn / loglogn ).It is commonly believed that deciding isomorphism between two graphs is strictly harder than deciding whether a graph has a nontrivial automorphism. Indeed, we show that an isomorphism oracle would improve the above result slightly–using such an oracle, one can decide whether there is an automorphism which moves at least k′ vertices, where k′ ∈ O(logn).If P $\ne$ NP and Graph Isomorphism is not NP-complete, the above results are fairly tight, since it is known that deciding if there is an automorphism which moves at least nε vertices, for any fixed ε ∈ (0, 1) , is NP-complete. In other words, a substantial improvement of our result would settle some fundamental open problems about Graph Isomorphism.