Canonical Forms for General Graphs Using Rooted Trees - Correctness and Complexity Study of the SCOTT Algorithm

Graph canonization (that solves also the graph isomorphism question) is an old problem that still attracts a lot of attention today, mainly because of the ubiquitous aspect of graph-based structures in computer science applications. This article present the proofs of correctness for the SCOTT algorithm, a graph canonization algorithm designed to provide a Canonical form for general graphs, namely graphs for which vertices and edges are coloured (labelled). These proofs ensure that the three canonical forms provided by SCOTT are valid, namely a canonical adjacency matrix, a canonical rooted tree (or DAG) and a canonical string. In addition, some crude lower and upper complexity bounds are presented and discussed. Finally some empirical evaluation is provided on a difficult synthetic benchmark with some comparison with the state of the art algorithms.