Document Open Access Logo

Hypergraph Isomorphism for Groups with Restricted Composition Factors

Author Daniel Neuen

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.88.pdf
  • Filesize: 0.54 MB
  • 19 pages

Document Identifiers

Author Details

Daniel Neuen
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany

Cite AsGet BibTex

Daniel Neuen. Hypergraph Isomorphism for Groups with Restricted Composition Factors. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 88:1-88:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.88

Abstract

We consider the isomorphism problem for hypergraphs taking as input two hypergraphs over the same set of vertices V and a permutation group Γ over domain V, and asking whether there is a permutation γ ∈ Γ that proves the two hypergraphs to be isomorphic. We show that for input groups, all of whose composition factors are isomorphic to a subgroup of the symmetric group on d points, this problem can be solved in time (n+m)^O((log d)^c) for some absolute constant c where n denotes the number of vertices and m the number of hyperedges. In particular, this gives the currently fastest isomorphism test for hypergraphs in general. The previous best algorithm for the above problem due to Schweitzer and Wiebking (STOC 2019) runs in time n^O(d)m^O(1). As an application of this result, we obtain, for example, an algorithm testing isomorphism of graphs excluding K_{3,h} as a minor in time n^O((log h)^c). In particular, this gives an isomorphism test for graphs of Euler genus at most g running in time n^O((log g)^c).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Graphs and surfaces
Keywords
  • graph isomorphism
  • groups with restricted composition factors
  • hypergraphs
  • bounded genus graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684-697. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897542.
  2. László Babai. Canonical form for graphs in quasipolynomial time: preliminary report. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1237-1246. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316356.
  3. László Babai, Peter J. Cameron, and Péter P. Pálfy. On the orders of primitive groups with restricted nonabelian composition factors. J. Algebra, 79(1):161-168, 1982. URL: https://doi.org/10.1016/0021-8693(82)90323-4.
  4. László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and John Wilmes. Faster canonical forms for strongly regular graphs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 157-166. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.25.
  5. László Babai and Paolo Codenotti. Isomorhism of hypergraphs of low rank in moderately exponential time. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 667-676. IEEE Computer Society, 2008. URL: https://doi.org/10.1109/FOCS.2008.80.
  6. László Babai, William M. Kantor, and Eugene M. Luks. Computational complexity and the classification of finite simple groups. In 24th Annual Symposium on Foundations of Computer Science, Tucson, Arizona, USA, 7-9 November 1983, pages 162-171. IEEE Computer Society, 1983. URL: https://doi.org/10.1109/SFCS.1983.10.
  7. László Babai and Eugene M. Luks. Canonical labeling of graphs. In David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas, editors, Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 171-183. ACM, 1983. URL: https://doi.org/10.1145/800061.808746.
  8. László Babai and John Wilmes. Quasipolynomial-time canonical form for steiner designs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 261-270. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488642.
  9. Christoph Berkholz, Paul S. Bonsma, and Martin Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory Comput. Syst., 60(4):581-614, 2017. URL: https://doi.org/10.1007/s00224-016-9686-0.
  10. Jin-yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identifications. Combinatorica, 12(4):389-410, 1992. URL: https://doi.org/10.1007/BF01305232.
  11. John D. Dixon and Brian Mortimer. Permutation groups, volume 163 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1996. URL: https://doi.org/10.1007/978-1-4612-0731-3.
  12. Michael Elberfeld and Ken-ichi Kawarabayashi. Embedding and canonizing graphs of bounded genus in logspace. In David B. Shmoys, editor, Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 383-392. ACM, 2014. URL: https://doi.org/10.1145/2591796.2591865.
  13. Martin Grohe and Dániel Marx. Structure theorem and isomorphism test for graphs with excluded topological subgraphs. SIAM J. Comput., 44(1):114-159, 2015. URL: https://doi.org/10.1137/120892234.
  14. Martin Grohe, Daniel Neuen, and Pascal Schweitzer. A faster isomorphism test for graphs of small degree. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 89-100. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00018.
  15. Martin Grohe, Daniel Neuen, Pascal Schweitzer, and Daniel Wiebking. An improved isomorphism test for bounded-tree-width graphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 67:1-67:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.67.
  16. Martin Grohe, Daniel Neuen, and Daniel Wiebking. Isomorphism testing for graphs excluding small minors. CoRR, abs/2004.07671, 2020. URL: http://arxiv.org/abs/2004.07671.
  17. Martin Grohe and Pascal Schweitzer. Isomorphism testing for graphs of bounded rank width. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1010-1029. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.66.
  18. Frank Harary. Graph theory. Addison-Wesley, 1991. Google Scholar
  19. Neil Immerman and Eric Lander. Describing graphs: A first-order approach to graph canonization. In Alan L. Selman, editor, Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, pages 59-81. Springer New York, New York, NY, 1990. URL: https://doi.org/10.1007/978-1-4612-4478-3_5.
  20. Ken-ichi Kawarabayashi. Graph isomorphism for bounded genus graphs in linear time. CoRR, abs/1511.02460, 2015. URL: http://arxiv.org/abs/1511.02460.
  21. Eugene M. Luks. Isomorphism of graphs of bounded valence can be tested in polynomial time. J. Comput. Syst. Sci., 25(1):42-65, 1982. URL: https://doi.org/10.1016/0022-0000(82)90009-5.
  22. Eugene M. Luks. Hypergraph isomorphism and structural equivalence of boolean functions. In Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton, editors, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA, pages 652-658. ACM, 1999. URL: https://doi.org/10.1145/301250.301427.
  23. Eugene M. Luks and Takunari Miyazaki. Polynomial-time normalizers. Discret. Math. Theor. Comput. Sci., 13(4):61-96, 2011. URL: http://dmtcs.episciences.org/531.
  24. Brendan D. McKay. Practical graph isomorphism. Congr. Numer., 30:45-87, 1981. Google Scholar
  25. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II. J. Symb. Comput., 60:94-112, 2014. URL: https://doi.org/10.1016/j.jsc.2013.09.003.
  26. Gary L. Miller. Isomorphism of graphs which are pairwise k-separable. Information and Control, 56(1/2):21-33, 1983. URL: https://doi.org/10.1016/S0019-9958(83)80048-5.
  27. Gary L. Miller. Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus. Information and Control, 56(1/2):1-20, 1983. URL: https://doi.org/10.1016/S0019-9958(83)80047-3.
  28. Daniel Neuen. Graph isomorphism for unit square graphs. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 70:1-70:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.70.
  29. Daniel Neuen. The Power of Algorithmic Approaches to the Graph Isomorphism Problem. PhD thesis, RWTH Aachen University, Aachen, Germany, 2019. URL: https://doi.org/10.18154/RWTH-2020-00160.
  30. Daniel Neuen. Hypergraph isomorphism for groups with restricted composition factors. CoRR, abs/2002.06997, 2020. URL: http://arxiv.org/abs/2002.06997.
  31. Ilia N. Ponomarenko. The isomorphism problem for classes of graphs closed under contraction. Journal of Soviet Mathematics, 55(2):1621-1643, 1991. URL: https://doi.org/10.1007/BF01098279.
  32. Gerhard Ringel. Das geschlecht des vollständigen paaren graphen. Abh. Math. Semin. Univ. Hambg., 28(3):139-150, 1965. URL: https://doi.org/10.1007/BF02993245.
  33. Joseph J. Rotman. An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics. Springer-Verlag, New York, fourth edition, 1995. URL: https://doi.org/10.1007/978-1-4612-4176-8.
  34. Pascal Schweitzer and Daniel Wiebking. A unifying method for the design of algorithms canonizing combinatorial objects. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1247-1258. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316338.
  35. Ákos Seress. Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2003. URL: https://doi.org/10.1017/CBO9780511546549.
  36. Xiaorui Sun and John Wilmes. Faster canonical forms for primitive coherent configurations: Extended abstract. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 693-702. ACM, 2015. URL: https://doi.org/10.1145/2746539.2746617.
  37. Daniel Wiebking. Graph isomorphism in quasipolynomial time parameterized by treewidth. CoRR, abs/1911.11257, 2019. URL: http://arxiv.org/abs/1911.11257.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact