Paper Info
Title
An exponential lower bound for individualization-refinement algorithms for graph isomorphism
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.
Year
DOI
Venue
2018
10.1145/3188745.3188900
STOC '18: Symposium on Theory of Computing Los Angeles CA USA June, 2018
Keywords
Field
DocType
graph isomorphism,canonization,individualization-refinement,lower bounds
Discrete mathematics,Heuristic,Polynomial,Graph isomorphism,Upper and lower bounds,Computer science,Algorithm,Isomorphism,Operator (computer programming),Invariant (mathematics),Worst-case complexity
Journal
Volume
ISSN
ISBN
abs/1705.03283
0737-8017
978-1-4503-5559-9
Citations 
PageRank 
References 
2
0.39
11
Authors
2
Name
Order
Citations
PageRank
Daniel Neuen195.03
Pascal Schweitzer221416.94