2017/05/09 by Daniel Neuen, Neuen, Daniel, Pascal Schweitzer +1 · 2 citations
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1705.03283
openalex publication_date 2017/05/09 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
The individualization-refinement paradigm provides a strong toolbox for\ntesting isomorphism of two graphs and indeed, the currently fastest\nimplementations of isomorphism solvers all follow this approach. While these\nsolvers are fast in practice, from a theoretical point of view, no general\nlower bounds concerning the worst case complexity of these tools are known. In\nfact, it is an open question whether individualization-refinement algorithms\ncan achieve upper bounds on the running time similar to the more theoretical\ntechniques based on a group theoretic approach.\n In this work we give a negative answer to this question and construct a\nfamily of graphs on which algorithms based on the individualization-refinement\nparadigm require exponential time. Contrary to a previous construction of\nMiyazaki, that only applies to a specific implementation within the\nindividualization-refinement framework, our construction is immune to changing\nthe cell selector, or adding various heuristic invariants to the algorithm.\nFurthermore, our graphs also provide exponential lower bounds in the case when\nthe k-dimensional Weisfeiler-Leman algorithm is used to replace the standard\ncolor refinement operator and the arguments even work when the entire\nautomorphism group of the inputs is initially provided to the algorithm.\n