Results
This site presents the notes for a now concluded project on CPQ query graph canonization. The final report titled CPQ Keys: a survey of graph canonization algorithms is available for reading and the repository with all the code is available at RoanH/CPQKeys.
Notes
- Overview of canonization algorithms
- Conjunctive Path Query (CPQ) Cores
- Conjunctive Path Query (CPQ) Syntax
- Language-aware Index
- Transforming directed graphs to undirected graphs
- Transforming edge labelled graphs to edge unlabelled graphs
- Treewidth
Literature
Extended notes for specific papers:
- A Logspace Algorithm for Partial 2-Tree Canonization (2008)
- A partial k-arboretum of graphs with bounded treewidth (1998)
- A unifying method for the design of algorithms canonizing combinatorial objects (2019)
- An Improved Isomorphism Test for Bounded-tree-width Graphs (2020)
- Attacks On Difficult Instances Of Graph Isomorphism: Sequential And Parallel Algorithms (2009)
- Canonical representations of partial 2- and 3-trees (1992)
- Canonizing Graphs of Bounded Tree Width in Logspace (2017)
- Practical graph isomorphism, II (2014)
- Scott A method for representing graphs as rooted trees for graph canonization (2019)
- The isomorphism problem for k-trees is complete for logspace (2012)
Current State
The current state of graph canonization for edge labelled directed graphs of treewidth 2 is not very rich. There are a lot of algorithms for undirected graphs without edge labels. Some of these algorithms even achieve very good runtimes with some extra assumptions (e.g. planar graph, DAG, trees). However, work on extending these existing techniques to edge labelled or directed graphs is fairly limited. Some algorithms that support directed graphs do exist, such as nauty, bliss and conauto. For edge labels Scott claims that it is the only algorithm that supports them (this claim is both in the original 2019 paper and in the 2020 follow up paper). Presently, this still seems to be the case as the original Scott paper has only been cited twice according to Google scholar. So far I have not found any algorithms that natively support both edge labels and directed graphs.