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

Nicolas Bloyet (1, 2) , Pierre-François Marteau (1) , Emmanuel Frénod (2)

1 EXPRESSION - Expressiveness in Human Centered Data/Media
2 LMBA - Laboratoire de Mathématiques de Bretagne Atlantique

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.

Mots clés: graph canonization; graph isomorphism; rooted tree; SCOTT algorithm; graph rewriting

Domaines: Algorithme et structure de données [cs.DS]; Recherche d'information [cs.IR]; Informatique [cs]

Nicolas Bloyet, Pierre-François Marteau, Emmanuel Frénod. Canonical Forms for General Graphs Using Rooted Trees - Correctness and Complexity Study of the SCOTT Algorithm. 2020. ⟨hal-02495229⟩