research-article

An exponential lower bound for individualization-refinement algorithms for graph isomorphism

Authors:

Pascal SchweitzerAuthors Info & Claims

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Pages 138 - 150

https://doi.org/10.1145/3188745.3188900

Published: 20 June 2018 Publication History

Abstract

The individualization-refinement paradigm provides a strong toolbox for testing isomorphism of two graphs and indeed, the currently fastest implementations of isomorphism solvers all follow this approach. While these solvers are fast in practice, from a theoretical point of view, no general lower bounds concerning the worst case complexity of these tools are known. In fact, it is an open question what the running time of individualization-refinement algorithms is. For all we know some of the algorithms could have polynomial running time.

In this work we give a negative answer to this question and construct a family of graphs on which algorithms based on the individualization-refinement paradigm require exponential time. Contrary to a previous construction of Miyazaki, that only applies to a specific implementation within the individualization-refinement framework, our construction is immune to changing the cell selector, the refinement operator, the invariant that is used, or adding various heuristic invariants to the algorithm. In fact, our graphs also provide exponential lower bounds in the case when the k-dimensional Weisfeiler-Leman algorithm is used to replace the the 1-dimensional Weisfeiler-Leman algorithm (often called color refinement) that is normally used. Finally, the arguments even work when the entire automorphism group of the inputs is initially provided to the algorithm. The arguments apply to isomorphism testing algorithms as well as canonization algorithms within the framework.

References

[1]

László Babai. 1979.

[2]

Monte Carlo algorithms in graph isomorphism testing. Technical Report 79-10. Université de Montréal.

[3]

László Babai. 1981. Moderately Exponential Bound for Graph Isomorphism. In Fundamentals of Computation Theory, FCT’81, Proceedings of the 1981 International FCT-Conference, Szeged, Hungary, August 24-28, 1981 (Lecture Notes in Computer Science), Ferenc Gécseg (Ed.), Vol. 117. Springer, 34–50. 3- 540- 10854- 8_4

Digital Library

[4]

László Babai. 2016. Graph isomorphism in quasipolynomial time. arXiv preprint arXiv:1512.03547 (2016).

[5]

László Babai. 2016.

[6]

Graph isomorphism in quasipolynomial time {extended abstract}. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, Daniel Wichs and Yishay Mansour (Eds.). ACM, 684–697.

Digital Library

[7]

László Babai, William M. Kantor, and Eugene M. Luks. 1983.

[8]

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. 162–171.

Digital Library

[9]

László Babai and Eugene M. Luks. 1983. Canonical Labeling of Graphs. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, 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 (Eds.). ACM, 171–183.

Digital Library

[10]

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.

[11]

Neil J. Calkin. 1997. Dependent Sets of Constant Weight Binary Vectors. Combinatorics, Probability & Computing 6, 3 (1997), 263–271. http://journals.cambridge. org/action/displayAbstract?aid=46529

Digital Library

[12]

Paolo Codenotti, Hadi Katebi, Karem A. Sakallah, and Igor L. Markov. 2013.

[13]

Conflict Analysis and Branching Heuristics in the Search for Graph Automorphisms. In 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, VA, USA, November 4-6, 2013. IEEE Computer Society, 907–914.

Digital Library

[14]

Merrick L. Furst, John E. Hopcroft, and Eugene M. Luks. 1980. Polynomial-Time Algorithms for Permutation Groups. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980. IEEE Computer Society, 36–41.

Digital Library

[15]

Mark.K. Goldberg. 1983.

[16]

A nonfactorial algorithm for testing isomorphism of two graphs. Discrete Applied Mathematics 6, 3 (1983), 229 – 236. 218X(83)90078- 1

[17]

Yuri Gurevich and Saharon Shelah. 1996. On Finite Rigid Structures. J. Symb. Log. 61, 2 (1996), 549–562.

[18]

Neil Immerman and Eric Lander. 1990.

[19]

Describing Graphs: A First-Order Approach to Graph Canonization. Springer New York, New York, NY, 59–81. org/10.1007/978- 1- 4612- 4478- 3_5

[20]

Tommi Junttila and Petteri Kaski. 2007.

[21]

Engineering an efficient canonical labeling tool for large and sparse graphs. In Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics, David Applegate, Gerth Stølting Brodal, Daniel Panario, and Robert Sedgewick (Eds.). SIAM, 135–149.

Digital Library

[22]

Tommi A. Junttila and Petteri Kaski. 2011.

[23]

Conflict Propagation and Component Recursion for Canonical Labeling. In Theory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings (Lecture Notes in Computer Science), Alberto Marchetti-Spaccamela and Michael Segal (Eds.), Vol. 6595. Springer, 151–162. 3- 642- 19754- 3_16 An Exponential Lower Bound for I/R-Algorithms for GI STOC’18, June 25–29, 2018, Los Angeles, CA, USA

Digital Library

[24]

José Luis López-Presa, Antonio Fernández Anta, and Luis Núñez Chiroque. 2011.

[25]

Conauto-2.0: Fast Isomorphism Testing and Automorphism Group Computation. CoRR abs/1108.1060 (2011).

[26]

Brendan D. McKay. 1981. Practical graph isomorphism. Congr. Numer. 30 (1981), 45–87.

[27]

Brendan D. McKay and Adolfo Piperno. 2014. Practical graph isomorphism, II. J. Symb. Comput. 60 (2014), 94–112.

Digital Library

[28]

Takunari Miyazaki. 1995. The complexity of McKay’s canonical labeling algorithm. In Groups and Computation (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), Vol. 28. DIMACS/AMS, 239–256.

[29]

Rajeev Motwani and Prabhakar Raghavan. 1995.

[30]

Randomized Algorithms. Cambridge University Press.

[31]

Daniel Neuen and Pascal Schweitzer. 2017.

[32]

Benchmark Graphs for Practical Graph Isomorphism. In 25th Annual European Symposium on Algorithms, ESA 2017, September 4-6, 2017, Vienna, Austria (LIPIcs), Kirk Pruhs and Christian Sohler (Eds.), Vol. 87. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 60:1–60:14.

[33]

Salil P. Vadhan. 2012. Pseudorandomness. Foundations and Trends in Theoretical Computer Science 7, 1-3 (2012), 1–336.

Digital Library

[34]

V. N. Zemlyachenko, N. M. Korneenko, and R. I. Tyshkevich. 1982. The graph isomorphism problem. Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 118 (1982), 83–158, 215. The theory of the complexity of computations, I. Abstract 1 Introduction 2 Preliminaries 2.1 Graphs 2.2 The Weisfeiler-Leman algorithm 3 Individualization-refinement algorithms 4 The multipede construction 5 The Weisfeiler-Leman refinement and the d-closure 6 Meager graphs 7 Lower bounds for individualization-refinement algorithms 8 Component Recursion 9 Discussion References

Cited By

Collins NLevet M(2024)Count-free Weisfeiler–Leman and group isomorphismInternational Journal of Algebra and Computation10.1142/S021819672450010334:03(283-330)Online publication date: 3-Apr-2024
https://doi.org/10.1142/S0218196724500103
Torán JWörz F(2023)Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism FormulasACM Transactions on Computational Logic10.1145/358047824:3(1-25)Online publication date: 7-Apr-2023
https://dl.acm.org/doi/10.1145/3580478
Grochow JLevet M(2023)On the Parallel Complexity of Group Isomorphism via Weisfeiler–LemanFundamentals of Computation Theory10.1007/978-3-031-43587-4_17(234-247)Online publication date: 18-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43587-4_17
Show More Cited By

Index Terms

An exponential lower bound for individualization-refinement algorithms for graph isomorphism
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
      1. Combinatorial algorithms
    2. Graph theory
      1. Graph algorithms
2. Theory of computation
  1. Design and analysis of algorithms
    1. Graph algorithms analysis

Recommendations

Planar Graph Isomorphism is in Log-Space
CCC '09: Proceedings of the 2009 24th Annual IEEE Conference on Computational Complexity

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We ...
Graph Isomorphism Parameterized by Elimination Distance to Bounded Degree

A commonly studied means of parameterizing graph problems is the deletion distance from triviality (Guo et al., Parameterized and exact computation, Springer, Berlin, pp. 162---173, 2004), which counts vertices that need to be deleted from a graph to ...
Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$ or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

June 2018

1332 pages

ISBN:9781450355599

DOI:10.1145/3188745

General Chairs:
Ilias Diakonikolas
University of Southern California, USA
,
David Kempe
University of Southern California, USA
,
Program Chair:
Monika Henzinger
University of Vienna, Austria

Copyright © 2018 ACM.

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].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '18

Sponsor:

SIGACT

STOC '18: Symposium on Theory of Computing

June 25 - 29, 2018

CA, Los Angeles, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
321
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Collins NLevet M(2024)Count-free Weisfeiler–Leman and group isomorphismInternational Journal of Algebra and Computation10.1142/S021819672450010334:03(283-330)Online publication date: 3-Apr-2024
https://doi.org/10.1142/S0218196724500103
Torán JWörz F(2023)Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism FormulasACM Transactions on Computational Logic10.1145/358047824:3(1-25)Online publication date: 7-Apr-2023
https://dl.acm.org/doi/10.1145/3580478
Grochow JLevet M(2023)On the Parallel Complexity of Group Isomorphism via Weisfeiler–LemanFundamentals of Computation Theory10.1007/978-3-031-43587-4_17(234-247)Online publication date: 18-Sep-2023
https://dl.acm.org/doi/10.1007/978-3-031-43587-4_17
Grohe MSchweitzer PWiebking DMarx D(2021)Deep weisfeiler lemanProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458218(2600-2614)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458218
Heid ELiu JAude AGreen W(2021)Influence of Template Size, Canonicalization, and Exclusivity for Retrosynthesis and Reaction Prediction ApplicationsJournal of Chemical Information and Modeling10.1021/acs.jcim.1c0119262:1(16-26)Online publication date: 23-Dec-2021
https://doi.org/10.1021/acs.jcim.1c01192
Grohe MSchweitzer P(2020)The graph isomorphism problemCommunications of the ACM10.1145/337212363:11(128-134)Online publication date: 22-Oct-2020
https://dl.acm.org/doi/10.1145/3372123
Benerecetti MDell'Erba DMogavero F(2019)Robust worst cases for parity games algorithmsInformation and Computation10.1016/j.ic.2019.104501(104501)Online publication date: Dec-2019
https://doi.org/10.1016/j.ic.2019.104501

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents