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

DOI10.1145/3188745.3188900zbMath1428.68166arXiv1705.03283OpenAlexW2963675331MaRDI QIDQ5230284

Pascal Schweitzer, Daniel Neuen

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1705.03283

zbMATH Keywords

lower boundsgraph isomorphismcanonizationindividualization-refinement

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas ⋮ Unnamed Item ⋮ Constructing Hard Examples for Graph Isomorphism ⋮ Benchmark Graphs for Practical Graph Isomorphism ⋮ Identifiability of Graphs with Small Color Classes by the Weisfeiler--Leman Algorithm

This page was built for publication: An exponential lower bound for individualization-refinement algorithms for graph isomorphism