Constructing Hard Examples for Graph Isomorphism.
Journal Title
J. Graph Algorithms Appl.
Publisher
Journal of Graph Algorithms and Applications
Volume
23
Number
2
Pages
293-316
Type
Article
This Version
AM
Metadata
Show full item recordCitation
Dawar, A., & Khan, K. (2019). Constructing Hard Examples for Graph Isomorphism.. J. Graph Algorithms Appl., 23 (2), 293-316. https://doi.org/10.7155/jgaa.00492
Abstract
We describe a method for generating graphs that provide difficult examples for practical Graph Isomorphism testers. We first give the theoretical construction, showing that we can have a family of graphs without any
non-trivial automorphisms which also have high Weisfeiler-Leman dimension. The construction is based on properties of random 3XOR-formulas.
We describe how to convert such a formula into a graph which has the
desired properties with high probability. We validate the method by experimental implementations. We construct random formulas and validate
them with a SAT solver to filter through suitable ones, and then convert
them into graphs. Experimental results demonstrate that the resulting
graphs do provide hard examples that match the hardest known benchmarks for graph isomorphism.
Sponsorship
Alan Turing Institute (Unknown)
Embargo Lift Date
2100-01-01
Identifiers
External DOI: https://doi.org/10.7155/jgaa.00492
This record's URL: https://www.repository.cam.ac.uk/handle/1810/300498
Rights
All rights reserved