search

digraphs / Digraphs

The GAP package Digraphs
https://digraphs.github.io/Digraphs
Other
30 stars 44 forks source link

Homomorphism finding is sometimes unreasonably slow #663

Open james-d-mitchell opened 3 months ago

james-d-mitchell commented 3 months ago

For example, 

gap> DigraphHomomorphism(NullDigraph(2), NullDigraph(64));
IdentityTransformation
gap> time;
1565

This seems to be because the homomorphism finding code finds a stabiliser chain for the symmetric group on 64 points, which is unreasonably slow, even though the very first attempt at finding a homomorphism would result in the IdentityTransformation being discovered. Not sure exactly how to fix this.