More Web Proxy on the site http://driver.im/

research-article

Hypergraph Isomorphism for Groups with Restricted Composition Factors

Author:

Daniel NeuenAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 18, Issue 3

Article No.: 27, Pages 1 - 50

https://doi.org/10.1145/3527667

Published: 11 October 2022 Publication History

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 this 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 (h ≥ 3) 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)}.

References

[1]

László Babai. 2015. Graph isomorphism in quasipolynomial time. arXiv:1512.03547. Retrieved from http://arxiv.org/abs/1512.03547v2.

[2]

László Babai. 2016. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, Daniel Wichs and Yishay Mansour (Eds.). ACM, 684–697. DOI:

Digital Library

[3]

László Babai, Peter J. Cameron, and Péter P. Pálfy. 1982. On the orders of primitive groups with restricted nonabelian composition factors. Journal of Algebra 79, 1 (1982), 161–168. DOI:

[4]

László Babai, Xi Chen, Xiaorui Sun, Shang-Hua Teng, and John Wilmes. 2013. Faster canonical forms for strongly regular graphs. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 157–166. DOI:

Digital Library

[5]

László Babai and Paolo Codenotti. 2008. Isomorhism of hypergraphs of low rank in moderately exponential time. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society, 667–676. DOI:

Digital Library

[6]

László Babai, William M. Kantor, and Eugene M. Luks. 1983. Computational complexity and the classification of finite simple groups. In Procceedings of the 24th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 162–171. DOI:

Digital Library

[7]

Christoph Berkholz, Paul S. Bonsma, and Martin Grohe. 2017. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems 60, 4 (2017), 581–614. DOI:

Digital Library

[8]

Jin-yi Cai, Martin Fürer, and Neil Immerman. 1992. An optimal lower bound on the number of variables for graph identifications. Combinatorica 12, 4 (1992), 389–410. DOI:

[9]

John D. Dixon and Brian Mortimer. 1996. Permutation groups. Graduate Texts in Mathematics, Vol. 163. Springer-Verlag, New York. xii+346 pages. DOI:

[10]

Michael Elberfeld and Ken-ichi Kawarabayashi. 2014. Embedding and canonizing graphs of bounded genus in logspace. In Proceedings of the Symposium on Theory of Computing, David B. Shmoys (Ed.). ACM, 383–392. DOI:

Digital Library

[11]

Martin Grohe and Daniel Neuen. 2021. Recent advances on the graph isomorphism problem. In Proceedings of the Surveys in Combinatorics, 2021: Invited lectures from the 28th British Combinatorial Conference, Konrad K. Dabrowski, Maximilien Gadouleau, Nicholas Georgiou, Matthew Johnson, George B. Mertzios, and Daniël Paulusma (Eds.). Cambridge University Press, 187–234. DOI:

[12]

Martin Grohe, Daniel Neuen, and Pascal Schweitzer. 2018. A faster isomorphism test for graphs of small degree. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science,Mikkel Thorup (Ed.). IEEE Computer Society, 89–100. DOI:

[13]

Martin Grohe, Daniel Neuen, and Pascal Schweitzer. 2018. A faster isomorphism test for graphs of small degree. arXiv:1802.04659v3. Retrieved from http://arxiv.org/abs/1802.04659v3.

[14]

Martin Grohe, Daniel Neuen, and Daniel Wiebking. 2020. Isomorphism testing for graphs excluding small minors. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, Sandy Irani (Ed.). IEEE, 625–636. DOI:

[15]

Frank Harary. 1991. Graph theory. Addison-Wesley.

[16]

John E. Hopcroft and Robert Endre Tarjan. 1971. A V\({^2}\) algorithm for determining isomorphism of planar graphs. Information Processing Letters 1, 1 (1971), 32–34. DOI:

[17]

John E. Hopcroft and Robert Endre Tarjan. 1972. Isomorphism of planar graphs. In Proceedings of the Symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York (The IBM Research Symposia Series), Raymond E. Miller and James W. Thatcher (Eds.). Plenum Press, New York, 131–152. DOI:

[18]

Neil Immerman and Eric Lander. 1990. Describing graphs: A first-order approach to graph canonization. In Proceedings of the Complexity Theory Retrospective: In Honor of Juris Hartmanis on the Occasion of His Sixtieth Birthday, July 5, 1988, Alan L. Selman (Ed.). Springer New York, New York, NY, 59–81. DOI:

[19]

Richard M. Karp. 1972. Reducibility among combinatorial problems. In Proceedings of a Symposium on the Complexity of Computer Computations, held March 20–22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York (The IBM Research Symposia Series), Raymond E. Miller and James W. Thatcher (Eds.). Plenum Press, New York, 85–103. DOI:

[20]

Ken-ichi Kawarabayashi. 2015. Graph isomorphism for bounded genus graphs in linear time. arXiv:1511.02460. Retrieved from http://arxiv.org/abs/1511.02460.

[21]

Eugene M. Luks. 1982. Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences 25, 1 (1982), 42–65. DOI:

[22]

Eugene M. Luks. 1999. Hypergraph isomorphism and structural equivalence of boolean functions. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, May 1–4, 1999, Atlanta, Georgia, Jeffrey Scott Vitter, Lawrence L. Larmore, and Frank Thomson Leighton (Eds.). ACM, 652–658. DOI:

Digital Library

[23]

Gary L. Miller. 1979. Graph isomorphism, general remarks. Journal of Computer and System Sciences 18, 2 (1979), 128–142. DOI:

[24]

Gary L. Miller. 1983. Isomorphism of graphs which are pairwise k-separable. Information and Control 56, 1/2 (1983), 21–33. DOI:

[25]

Gary L. Miller. 1983. Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus. Information and Control 56, 1/2 (1983), 1–20. DOI:

[26]

Daniel Neuen. 2016. Graph isomorphism for unit square graphs. In Proceedings of the 24th Annual European Symposium on Algorithms, Aarhus, Denmark (LIPIcs), Piotr Sankowski and Christos D. Zaroliagis (Eds.), Vol. 57. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 70:1–70:17. DOI:

[27]

Daniel Neuen. 2019. The Power of Algorithmic Approaches to the Graph Isomorphism Problem. Ph.D. Dissertation. RWTH Aachen University, Aachen, Germany. DOI:

[28]

Daniel Neuen. 2020. Hypergraph isomorphism for groups with restricted composition factors. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany (Virtual Conference) (LIPIcs), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.), Vol. 168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 88:1–88:19. DOI:

[29]

Daniel Neuen. 2021. Isomorphism testing parameterized by genus and beyond. In Proceedings of the 29th Annual European Symposium on Algorithms,Petra Mutzel, Rasmus Pagh, and Grzegorz Herman (Eds.), Vol. 204. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 72:1–72:18. DOI:

[30]

Daniel Neuen. 2022. Isomorphism testing for graphs excluding small topological subgraphs. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference, Joseph S. Naor and Niv Buchbinder (Eds.). SIAM, 1411–1434. DOI:

[31]

Ilia N. Ponomarenko. 1989. The isomorphism problem for classes of graphs. Doklady Akademii Nauk SSSR 304, 3 (1989), 552–556.

[32]

Ilia N. Ponomarenko. 1991. The isomorphism problem for classes of graphs closed under contraction. Journal of Soviet Mathematics 55, 2 (01 Jun 1991), 1621–1643. DOI:

[33]

Gerhard Ringel. 1965. Das geschlecht des vollständigen paaren graphen. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg 28, 3 (01 Oct 1965), 139–150. DOI:

[34]

Joseph J. Rotman. 1995. An Introduction to the Theory of Groups (fourth ed.). Graduate Texts in Mathematics, Vol. 148. Springer-Verlag, New York. xvi+513 pages. DOI:

[35]

Pascal Schweitzer and Daniel Wiebking. 2019. A unifying method for the design of algorithms canonizing combinatorial objects. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ,Moses Charikar and Edith Cohen (Eds.). ACM, 1247–1258. DOI:

Digital Library

[36]

Ákos Seress. 2003. Permutation group algorithms. Cambridge Tracts in Mathematics, Vol. 152. Cambridge University Press, Cambridge. x+264 pages. DOI:

[37]

Daniel Wiebking. 2020. Graph isomorphism in quasipolynomial time parameterized by treewidth. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, Saarbrücken, Germany (Virtual Conference) (LIPIcs), Artur Czumaj, Anuj Dawar, and Emanuela Merelli (Eds.), Vol. 168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 103:1–103:16. DOI:

Cited By

Neuen D(2024)Isomorphism Testing for Graphs Excluding Small Topological SubgraphsACM Transactions on Algorithms10.1145/365198620:3(1-43)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3651986
Neuen D(2024)Isomorphism Testing Parameterized by Genus and BeyondSIAM Journal on Discrete Mathematics10.1137/22M151407638:1(453-484)Online publication date: 22-Jan-2024
https://doi.org/10.1137/22M1514076
Grohe MNeuen DWiebking D(2023)Isomorphism Testing for Graphs Excluding Small MinorsSIAM Journal on Computing10.1137/21M140193052:1(238-272)Online publication date: 28-Feb-2023
https://doi.org/10.1137/21M1401930

Index Terms

Hypergraph Isomorphism for Groups with Restricted Composition Factors
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
      2. Graphs and surfaces
2. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Selective hypergraph colourings

We look at colourings of r -uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge E in an r -uniform hypergraph H whose vertices are coloured is the partition of r induced by the ...
Isomorphism criterion for monomial graphs

Let q be a prime power, 𝔽_q be the field of q elements, and k, m be positive integers. A bipartite graph G = G_q(k, m) is defined as follows. The vertex set of G is a union of two copies P and L of two-dimensional vector spaces over 𝔽_q, with two ...
A Faster Isomorphism Test for Graphs of Small Degree

In a recent breakthrough, Babai [Proceedings of STOC, ACM, New York, 2016, pp. 684--697] gave a quasipolynomial-time graph isomorphism test. In this work, we give an improved isomorphism test for graphs of small degree: our algorithm runs in time $n^{\...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 18, Issue 3

July 2022

314 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3561945

Editor:
Edith Cohen
Google Research, USA and Tel Aviv University, Israel

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 October 2022

Online AM: 21 April 2022

Accepted: 18 March 2022

Revised: 25 January 2022

Received: 11 December 2020

Published in TALG Volume 18, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
158
Total Downloads

Downloads (Last 12 months)38
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Neuen D(2024)Isomorphism Testing for Graphs Excluding Small Topological SubgraphsACM Transactions on Algorithms10.1145/365198620:3(1-43)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.1145/3651986
Neuen D(2024)Isomorphism Testing Parameterized by Genus and BeyondSIAM Journal on Discrete Mathematics10.1137/22M151407638:1(453-484)Online publication date: 22-Jan-2024
https://doi.org/10.1137/22M1514076
Grohe MNeuen DWiebking D(2023)Isomorphism Testing for Graphs Excluding Small MinorsSIAM Journal on Computing10.1137/21M140193052:1(238-272)Online publication date: 28-Feb-2023
https://doi.org/10.1137/21M1401930

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View full text|Download PDF

View Issue’s Table of Contents