Permutation Groups and the Graph Isomorphism Problem - Perspectives in Computational Complexity - page 195

blocks whose computation allows us to often reduce the general case to the primitive
case. Also in most of these cases the primitive case is solvable if the group is known
to be in some special class like solvable or

d . This makes use of bounds on the
sizes of primitive groups or, in some cases, their explicit structure. We also saw how
these classes naturally arose in study of restricted versions of graph isomorphism. We
therefore believe that a better understanding of permutation groups and is relation to
graph isomorphism is crucial in pinning down the computational complexity of this
elusive problem.

References

[AK02] V. Arvind, P.P. Kurur, Graph Isomorphism is in SPP in 43rd Annual IEEE Symposium
of Foundations of Computer Science, November 2002, pp. 743-750.
[AKV05] V. Arvind, P.P. Kurur, T.C. Vijayaraghavan, Bounded color multiplicity graph isomor-
phism is in the #L hierarchy in 20th IEEE Conference on Computational Complexity
(CCC 2005), June 2005, pp. 13-27.
[BL83] L. Babai, E.M. Luks, Canonical labeling of graphs. in Proceedings of the Fifteenth
Annual ACM Symposium on Theory of, Computing, 1983, pp. 171-183.
[BCP82] L. Babai, P.J. Cameron, P.P. Pálfy, On the order of primitive groups with restricted
nonabelian composition factors. J. Algebra. 79 , 161-168 (1982)
[BHZ87] R. Boppana, J. Hastad, S. Zachos, Does co-NP have short interactive proofs. Inf.
Process. Lett. 25 (2), 127-132 (1987)
[DM91] J.D. Dixon B. Mortimer, Permutation Groups. Graduate Texts in Mathematics,
vol 163, (Springer, New York, 1991).
[DK09] S. Dutta, P.P. Kurur, Representating groups on graphs. CoRR, abs/0904.3941 (2009).
[DLNTW09] S. Dutta, N. Limaye, P. Nimbhorkar, T. Thierauf, F. Wagner, Planar graph isomor-
phism is in logspace. in Proceedings of the IEEE Conference on Computational Com-
plexity, 2009, pp 124-203.
[FT63] W. Feit, J.G. Thompson, Solvability of groups of odd order. Pac. J. Math. 13(3), 775-
1027, (1963). URL http://projecteuclid.org/euclid.pjm/1103053943
[FFK91] S.A. Fenner, L. Fortnow, S.A. Kurtz, Gap-definable counting classes. in Structure
in Complexity Theory Conference, 1991, pp 30-42. URL http://citeseer.nj.nec.com/
fenner92gapdefinable.html
[FHL80] M.L. Furst, J.E. Hopcroft, E.M. Luks, Polynomial-time algorithms for permutation
groups. in IEEE Symposium on Foundations of Computer, Science, 1980, pp. 36-41.
[GJ79] M. Garey, D. Johnson, Computers and intractability: a guide to the theory of NP-
completeness (W. H. Freeman, New York, 1979)
[Hal59] M. Hall Jr., The Theory of Groups , 1st edn. (The Macmillan Company, New York,
1959)
[HW74] J.E. Hopcroft, J.K. Wong, Linear time algorithm for isomorphism of planar graphs
(preliminary report). in Proceedings of the Sixth Annual ACM Symposium on Theory
of Computing, STOC '74 (ACM, New York, 1974), pp. 172-184.
[KST92] J. Köbler, U. Schöning, J. Torán, Graph isomorphism is low for pp. Comput. Complex.
2(4), 301-330 (1992) URL http://citeseer.nj.nec.com/obler92graph.html
[KST93] J. Köbler, U. Schöning, J. Torán, The Graph Isomorphism Problem: Its Structural
Complexity (Birkhauser, Switzerland, 1993)
[Kur06] P.P. Kurur, Complexity upper bounds using permutation group theory. PhD thesis,
Institute of Mathematical Sciences, Chennai, India, 2006.
[Lad75] R.E. Ladner, On the structure of polynomial time reducibility. J. ACM 22 (1), 155-171
(1975)