Constructing Hard Examples for Graph Isomorphism.
J. Graph Algorithms Appl.
Journal of Graph Algorithms and Applications
MetadataShow full item record
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
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.
Alan Turing Institute (Unknown)
Embargo Lift Date
External DOI: https://doi.org/10.7155/jgaa.00492
This record's URL: https://www.repository.cam.ac.uk/handle/1810/300498
All rights reserved