Title :
A note on decision versus search for graph automorphism
Author :
Agrawal, M. ; Arvind, V.
Author_Institution :
Abteilung Theoretische Inf., Ulm Univ., Germany
Abstract :
We show that for any graph G, k non-trivial automorphisms of G-if as many exist-can be computed in time |G|O(log k) with nonadaptive queries to GA, the decision problem for Graph Automorphism. As a consequence we show that some problems related to GA and GI are polynomial-time truth-table equivalent to GA
Keywords :
computational complexity; decision theory; graph theory; search problems; Graph Automorphism; Graph Isomorphism problem; decision; polynomial-time; search; truth-table equivalent; Computer science; Mathematics; NP-complete problem; Polynomials; Testing;
Conference_Titel :
Computational Complexity, 1996. Proceedings., Eleventh Annual IEEE Conference on
Conference_Location :
Philadelphia, PA
Print_ISBN :
0-8186-7386-9
DOI :
10.1109/CCC.1996.507689
