nauty and Traces

Graphs in some applications, such as constraint satisfaction problems described by saucy have many small components with vertices of low degree, vertices with common neighborhoods, and so on. saucy handles them efficiently by a refinement procedure tuned to this situation plus early detection of sparse automorphisms. Traces employs another method. Recall that after the first refinement vertices with equal colours also have equal degrees. The target cell selector never selects cells containing vertices of degree 0, 1, 2 or n-1, and nodes whose non-trivial cells are only of those degrees are not expanded further. Special-purpose code then produces generators for the automorphism group fixed by the node and, if necessary, a unique discrete colouring that refines the node. This technique is quite successful. However, in our opinion, graphs of this type ought to be handled by preprocessing. For example, sets of vertices with the same neighborhoods ought to be replaced by single vertices with a colour that encodes the multiplicity. All tree-like appendages, long paths of degree 2 vertices, and similar easy subgraphs, could be efficiently factored out in this manner.