Post #117

Discovering automorphism of a graph and its deck. My hypothesis was that if you take some hard graph for graph isomorphism problem and remove one vertex, then the resulted graph will be much easier because the symmetry of the original graph will be broken. So I took the hardest known graphs for graph isomorphism and checked how much time it takes for determining automorphism group (which is similar to how hard it would be to run isomorphism test). The results are quite interesting. Indeed for many subgraphs determining automorphism is 50-100 times easier. But surprisingly, there are subgraphs which are harder than the original graph. In the image below, you can see results for 6 graphs from cfi-rigid-z2 with ~1000-2000 vertices and checked the runtime for the original graph and all possible subgraphs by deleting one vertex. You can see that while for the first two graphs (first row), all subgraphs are easier, for the next 4 graphs, there are smaller subgraphs that take 5x more time to solve that the original graph. This could happen for three reasons: (1) nauty solver has some heuristics that worked better for the original graph than for the subgraphs (2) not stable running and rerunning it would result in different runtimes and (3) smaller graphs somehow indeed harder than the original graph. I think (2) is very unlikely and my guess is a combination of (1) and (3): removing a vertex makes equivalent vertices in the original graph to be non-equivalent in the subgraph which reduces the amount of pruning nauty does.