On the complexity of identifying strongly regular graphs. (English) Zbl 1527.05178
Summary: In this paper, we show that Graph Isomorphism (GI) is not \(AC^0\) reducible to several problems, including the Latin Square Isotopy problem, isomorphism testing of several families of Steiner designs, and isomorphism testing of conference graphs. As a corollary, we obtain that \(GI\) is not \(AC^0\)-reducible to isomorphism testing of Latin square graphs and strongly regular graphs arising from special cases of Steiner 2-designs. We accomplish this by showing that the generator-enumeration technique for each of these problems can be implemented in \(\beta_2\mathsf{FOLL}\), which cannot compute Parity [A. Chattopadhyay et al., ACM Trans. Comput. Theory 5, No. 4, Article No. 13, 13 p. (2013; Zbl 1322.68096)].
MSC:
| 05E30 | Association schemes, strongly regular graphs |
| 05B15 | Orthogonal arrays, Latin squares, Room squares |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
Citations:
Zbl 1322.68096References:
| [1] | A. A. Albert, Quasigroups. I, Trans. Amer. Math. Soc. 54 (1943), 507-519. doi:10.2307/1990259 · Zbl 0063.00039 · doi:10.2307/1990259 |
| [2] | S. Arora and B.Barak, Computational Complexity: A Modern Approach, Cam-bridge: Cambridge University Press, (2009). doi:10.1017/CBO9780511804090 · Zbl 1193.68112 · doi:10.1017/CBO9780511804090 |
| [3] | V. Arvind and P. P. Kurur, Graph Isomorphism is in SPP, Inform. and Comput. 204 (2006), 835-852. doi:10.1016/j.ic.2006.02.002 · Zbl 1110.68090 · doi:10.1016/j.ic.2006.02.002 |
| [4] | L. Babai, On the Complexity of Canonical Labeling of Strongly Regular Graphs, SIAM J. Comput. 9 (1980), 212-216. doi:10.1137/0209018 · Zbl 0446.68052 · doi:10.1137/0209018 |
| [5] | L. Babai, On the Order of Uniprimitive Permutation Groups, Ann. Math. 113 (1981), 553-568. doi:10.2307/2006997 · Zbl 0485.20002 · doi:10.2307/2006997 |
| [6] | L. Babai, On the Automorphism Groups of Strongly Regular Graphs I, In Proc. 5th Conf. on Innovations in Theoret. Comp. Sci., ITCS ’14, pp. 359-368, New York, NY, USA, (2014). Association for Computing Machinery. doi:10.1145/2554797.2554830 · Zbl 1365.05202 · doi:10.1145/2554797.2554830 |
| [7] | L. Babai, Graph isomorphism in quasipolynomial time [extended abstract], In STOC’16-Proc. 48th Annual ACM SIGACT Symposium on Theory of Computing, pp. 684-697. New York, NY, USA, (2016). Association for Computing Machinery. Preprint of full version: arXiv:1512.03547v2 [cs.DS]. doi:10.1145/2897518.2897542 · Zbl 1376.68058 · doi:10.1145/2897518.2897542 |
| [8] | L. Babai, W. M. Kantor and E. M. Luks, Computational complexity and the classification of finite simple groups, In 24th Annual Symposium on Foundations of Computer Science (SFCS 1983), pp. 162-171. doi:10.1109/SFCS.1983.10 · doi:10.1109/SFCS.1983.10 |
| [9] | L. Babai and E. M. Luks, Canonical Labeling of Graphs, In Proc. Fif-teenth Annual ACM Symposium on Theory of Computing (STOC 1983), 171-183; New York, NY, USA, (1983); Association for Computing Machinery. doi:10.1145/800061.808746 · doi:10.1145/800061.808746 |
| [10] | L. Babai and J. Wilmes, Quasipolynomial-Time Canonical Form for Steiner Designs, In Proc. forty-fifth annual ACM Symposium on Theory of Comput-ing (STOC 2013), pp. 261-270, New York, NY, USA, (2013); Association for Computing Machinery. doi:10.1145/2488608.2488642 · Zbl 1293.05028 · doi:10.1145/2488608.2488642 |
| [11] | D. Barrington, P. Kadau, K. Lange and P. McKenzie, On the Complexity of Some Problems on Groups Input as Multiplication Tables, J. Comput. Syst. Sci. 63 (2001), 186-200. doi:10.1006/jcss.2001.1764. · Zbl 0988.68080 · doi:10.1006/jcss.2001.1764 |
| [12] | H. U. Besche and B. Eick, Construction of finite groups, J. Symb. Comput. 27 (1999), 387-404. doi:10.1006/jsco.1998.0258 · Zbl 0922.20001 · doi:10.1006/jsco.1998.0258 |
| [13] | H. U. Besche, B. Eick and E. A. O’Brien, A Millennium Project: Constructing Small Groups, Intern. J. Alg. and Comput. 12 (2002), 623-644. doi:10.1142/S0218196702001115 · Zbl 1020.20013 · doi:10.1142/S0218196702001115 |
| [14] | R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math. 13 (1963), 389-419. doi:pjm/1103035734 · Zbl 0118.33903 |
| [15] | R. H. Bruck, Finite nets II, Uniqueness and imbedding, Pacific J. Math. 13 (1963), 421-457. doi:10.2140/pjm.1963.13.421 · Zbl 0124.00903 · doi:10.2140/pjm.1963.13.421 |
| [16] | H. Buhrman and S. Homer, Superpolynomial Circuits, Almost Sparse Ora-cles and the Exponential Hierarchy, In: Foundations of Software Technology and Theoretical Computer Science, 12th Conf., New Delhi, India, Dec. 18-20, 1992, Proceedings vol. 652 of Lec. Notes in Comp. Sci., pp. 116-127, Springer. doi:10.1007/3-540-56287-7 99 · Zbl 0925.68183 · doi:10.1007/3-540-56287-7_99 |
| [17] | J. Y. Cai, M. F’urer and N. Immerman, An optimal lower bound on the num-ber of variables for graph identification, Combinatorica 12 (1992), 389-410; · Zbl 0785.68043 |
| [18] | Originally appeared in SFCS ’89. doi:10.1007/BF01305232 · Zbl 0785.68043 · doi:10.1007/BF01305232 |
| [19] | J. J. Cannon and D. F. Holt, Automorphism group computation and isomor-phism testing in finite groups, J. Symb. Comput. 35 (2003), 241-267. doi:10.1016/S0747-7171(02)00133-5 · Zbl 1032.20016 · doi:10.1016/S0747-7171(02)00133-5 |
| [20] | A. Chattopadhyay, J. Torán and F. Wagner, Graph isomorphism is not AC 0 -reducible to group isomorphism, ACM Trans. Comput. Theory 5 (2013), 1-13. doi:10.1145/2540088 · Zbl 1322.68096 · doi:10.1145/2540088 |
| [21] | X. Chen, X. Sun and S. Teng, Multi-Stage Design for Quasipolynomial-Time Isomorphism Testing of Steiner 2-Systems, In: Proc. Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2013), pp. 271-280, New York, NY, USA (2013); Association for Computing Machinery. doi:10.1145/2488608.2488643 · Zbl 1293.05223 · doi:10.1145/2488608.2488643 |
| [22] | M. J. Colbourn and C. J. Colbourn, Concerning the complexity of deciding isomorphism of block designs, Discret. Appl. Math. 3 (1981), 155-162. doi:10.1016/0166-218X(81)90012-3 · Zbl 0475.05075 · doi:10.1016/0166-218X(81)90012-3 |
| [23] | M. J. Colbourn and R. A. Mathon, On Cyclic Steiner 2-Designs, In: Topics on Steiner Systems (Eds.: C. C. Linder and A. Rosa), Ann. Discrete Math. Vol. 7, pp. 215-253, Elsevier (1980). doi:10.1016/S0167-5060(08)70182-1 · Zbl 0438.05012 · doi:10.1016/S0167-5060(08)70182-1 |
| [24] | M. J. Colbourn, An analysis technique for Steiner triple systems, In: Proc. 10th Southeastern Conf. on Combin., Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), Congr. Numer. 2 (1979), 289-303. · Zbl 0426.05010 |
| [25] | D. G. Corneil and C. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism, J. ACM 17 (1970), 51-64. doi:10.1145/321556.321562 · Zbl 0199.27801 · doi:10.1145/321556.321562 |
| [26] | B. Eick, C. R. Leedham-Green and E. A. O’Brien, Constructing automorphism groups of p-groups, Comm. Algebra 30 (2002), 2271-2295. doi:10.1081/AGB-120003468 · Zbl 1006.20001 · doi:10.1081/AGB-120003468 |
| [27] | M. Grohe and O. Verbitsky, Testing Graph Isomorphism in Parallel by Playing a Game, In: Automata, Languages and Programming, 33rd Int. Coll., ICALP 2006, Venice, Italy, July 10-14, 2006, Proc., Part I; Lec. Notes in Comp. Sci. 4051, pp. 3-14, Springer. doi:10.1007/11786986 2 · Zbl 1223.68056 · doi:10.1007/11786986_2 |
| [28] | M. Huber, Computational complexity of reconstruction and isomorphism testing for designs and line graphs, J. Combin. Theory Ser. A. 118 (2011), 341-349. doi:10.1016/j.jcta.2010.06.006 · Zbl 1225.05182 · doi:10.1016/j.jcta.2010.06.006 |
| [29] | R. Impagliazzo, R. Paturi and F. Zane, Which Problems Have Strongly Expo-nential Complexity?, J. Comput. Syst. Sci. 63 (2001), 512-530. doi:10.1006/jcss.2001.1774 · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774 |
| [30] | S. Kiefer, Power and Limits of the Weisfeiler-Leman Algorithm, Ph.D. Thesis, RWTH Aachen University (2019). · Zbl 1541.68291 |
| [31] | J. Köbler, U. Schöning and J. Torán, Graph Isomorphism is Low for PP, Com-put. Complex. 2 (1992), 301-330. doi:10.1007/BF01200427 · Zbl 0770.68055 · doi:10.1007/BF01200427 |
| [32] | R. E. Ladner, On the Structure of Polynomial Time Reducibility, J. ACM, 22 (1975), 155-171. doi:10.1145/321864.321877 · Zbl 0322.68028 · doi:10.1145/321864.321877 |
| [33] | F. Le Gall and D. J. Rosenbaum, On the Group and Color Isomorphism Prob-lems, (2016), arXiv:1609.08253 [cs.CC]. |
| [34] | L. Lovász, On the ratio of optimal integral and fractional covers, Discrete Math. 13 (1975), 383-390. doi:10.1016/0012-365X(75)90058-8 · Zbl 0323.05127 · doi:10.1016/0012-365X(75)90058-8 |
| [35] | E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polyno-mial time, J. Comput. Syst. Sci. 25 (1982), 42-65. doi:10.1016/0022-0000(82)90009-5 · Zbl 0493.68064 · doi:10.1016/0022-0000(82)90009-5 |
| [36] | R. Mathon, A note on the graph isomorphism counting problem, Inf. Process. Lett. 8 (1979), 131-136. doi:10.1016/0020-0190(79)90004-8 · Zbl 0395.68057 · doi:10.1016/0020-0190(79)90004-8 |
| [37] | G. L. Miller, On the n log n Isomorphism Technique (A Preliminary Report), In Proc. Tenth Annual ACM Symposium on Theory of Computing (STOC 1978), pp. 51-58, New York, NY, USA, (1978); Association for Computing Machinery. doi:10.1145/800133.804331 · Zbl 1282.68192 · doi:10.1145/800133.804331 |
| [38] | H. Nakasora, Mutually Orthogonal Latin Squares and Self-complementary De-signs, Math. J. Okayama Univ. 48 (2006), 21-31. https://api.semanticscholar.org/CorpusID:122686932 · Zbl 1132.05010 |
| [39] | D. Neuen and P. Schweitzer, An exponential lower bound for individualization-refinement algorithms for graph isomorphism, In: Proc. 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pp. 138-150, New York, NY, USA, (2018); Association for Computing Machinery. doi:10.1145/3188745.3188900 · Zbl 1428.68166 · doi:10.1145/3188745.3188900 |
| [40] | A. Neumaier, Strongly regular graphs with smallest eigenvalue −m, Arch. Math. 33 (1979), 392-400. doi:10.1007/BF01222774 · Zbl 0407.05043 · doi:10.1007/BF01222774 |
| [41] | D. K. Ray-Chaudhuri and R. M. Wilson, On t-designs, Osaka J. Math. 12 (1975), 737-744. doi:10.18910/7296 · Zbl 0342.05018 · doi:10.18910/7296 |
| [42] | D. J. Rosenbaum, Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing, (2013) arXiv:1304.3935 [cs.DS]. |
| [43] | D. C. Schmidt and L. E. Druffel, A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance Matrices, J. ACM 23 (1976), 433-445. doi:10.1145/321958.321963 · Zbl 0357.05049 · doi:10.1145/321958.321963 |
| [44] | U. Schöning, Graph isomorphism is in the low hierarchy, J. Comput. Syst. Sci. 37 (1988), 312-323. doi:10.1016/0022-0000(88)90010-4 · Zbl 0666.68048 · doi:10.1016/0022-0000(88)90010-4 |
| [45] | T. Schrock and R. Frongillo, Computational complexity of k-block conjugacy, Theor. Comput. Sci. 856 (2021), 21-40. doi:10.1016/j.tcs.2020.12.009 · Zbl 1477.37023 · doi:10.1016/j.tcs.2020.12.009 |
| [46] | R. Smolensky, Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity, In: Proc. 19th Annual ACM Symposium on Theory of Computing, 1987 (STOC 1987), pp. 77-82, New York, New York, USA, (1987) Association for Computing Machinery. doi:10.1145/28395.28404 · doi:10.1145/28395.28404 |
| [47] | D. A. Spielman, Faster Isomorphism Testing of Strongly Regular Graphs, In: Proc. Twenty-Eighth Annual ACM Symposium on Theory of Computing, 1996 (STOC 1996), pp. 576-584; New York, NY, USA, (1996), Association for Com-puting Machinery. doi:10.1145/237814.238006 · Zbl 0915.05104 · doi:10.1145/237814.238006 |
| [48] | M. Suzuki, A simple group of order 448, 345, 497, 600, Theory of finite groups (1969), 113-119. · Zbl 0205.32502 |
| [49] | B. Tang, Towards Understanding Satisfiability, Group Isomorphism and Their Connections, Ph.D. Thesis, Tsinghua University (2013), http://papakonstantinou.org/periklis/pdfs/bangsheng thesis.pdf |
| [50] | J. Torán, On the Hardness of Graph Isomorphism, SIAM J. Comput. 33 (2004), 1093-1108. doi:10.1137/S009753970241096X · Zbl 1055.05106 · doi:10.1137/S009753970241096X |
| [51] | H. Vollmer Introduction to Circuit Complexity -A Uniform Approach, Texts in Theoretical Computer Science; An EATCS Series, Springer (1999). doi:10.1007/978-3-662-03927-4 · doi:10.1007/978-3-662-03927-4 |
| [52] | J. B. Wilson, The Threshold for Subgroup Profiles to Agree is Logarithmic, Theory Comput. 15 (2019), 1-25. doi:10.4086/toc.2019.v015a019 · Zbl 1494.68100 · doi:10.4086/toc.2019.v015a019 |
| [53] | M. J. Wolf, Nondeterministic circuits, space complexity and quasigroups, Theor. Comput. Sci. 125 (1994), 295-313. doi:10.1016/0304-3975(92)00014-I · Zbl 0795.68074 · doi:10.1016/0304-3975(92)00014-I |
| [54] | V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich, Graph isomor-phism problem, J. Sov. Math. 29 (1985), 1426-1481. doi:10.1007/BF02104746 · Zbl 0564.05049 · doi:10.1007/BF02104746 |
| [55] | Complexity Zoo, https://complexityzoo.net . (Received 16 July 2022; revised 23 Mar 2023, 17 Aug 2023) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
