Geodesic
Constructing Hard Examples for Graph Isomorphism
Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 293-316.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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.
DOI : 10.7155/jgaa.00492
Keywords: graph isomorphism, Weisfeiler-Leman, experiments, satisfiability 
@article{JGAA_2019_23_2_a6,
     author = {Anuj Dawar and Kashif Khan},
     title = {Constructing {Hard} {Examples} for {Graph} {Isomorphism}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {293--316},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2019},
     doi = {10.7155/jgaa.00492},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00492/}
}
TY  - JOUR
AU  - Anuj Dawar
AU  - Kashif Khan
TI  - Constructing Hard Examples for Graph Isomorphism
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 293
EP  - 316
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00492/
DO  - 10.7155/jgaa.00492
LA  - en
ID  - JGAA_2019_23_2_a6
ER  - 
%0 Journal Article
%A Anuj Dawar
%A Kashif Khan
%T Constructing Hard Examples for Graph Isomorphism
%J Journal of Graph Algorithms and Applications
%D 2019
%P 293-316
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00492/
%R 10.7155/jgaa.00492
%G en
%F JGAA_2019_23_2_a6
Anuj Dawar; Kashif Khan. Constructing Hard Examples for Graph Isomorphism. Journal of Graph Algorithms and Applications, Tome 23 (2019) no. 2, pp. 293-316. doi : 10.7155/jgaa.00492. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00492/

Cité par Sources :