Search Space Contraction in Canonical Labeling of Graphs (Preliminary Version)

Abstract

The individualization-refinement paradigm for computing a canonical labeling and/or the automorphism group of a graph is investigated. New techniques are introduced with the aim of reducing the size of the associated search space. In particular, a new partition refinement algorithm is proposed, together with graph invariants having a global nature. Experimental results and comparisons with existing tools, such as nauty, reveal that the presented approach produces a huge contraction of the search space. Such reduction will be shown to be exponential for special classes of graphs which are intractable by nauty.