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

---

Link: https://hal.archives-ouvertes.fr/hal-02495229/

Abstract: 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.

---

This paper is a follow up paper containing extra proofs for the original Scott paper. The most important detail for this paper is the following statement on extending the approach to direct graphs:

As a perspective, a generalization of Scott to handle oriented graphs, typically used in the representation of social relations or dependencies, could be quite easily considered by adapting the set of productions used to transform a graph into an equivalent tree. Since a rooted tree with non-oriented edges is equivalent to the same rooted tree with oriented edges, the trace function once the tree is obtained would be usable without any modification. However, the validity of this extension remains to be asserted.