Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00492
Constructing Hard Examples for Graph Isomorphism
Vol. 23, no. 2, pp. 293-316, 2019. Regular paper.
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.
|
Submitted: September 2018.
Reviewed: January 2019.
Revised: March 2019.
Accepted: March 2019.
Final: April 2019.
Published: April 2019.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|