A unifying method for the design of algorithms canonizing combinatorial objects (2019)


Link: https://dl.acm.org/doi/abs/10.1145/3313276.3316338

Abstract: We devise a unified framework for the design of canonization algorithms. Using hereditarily finite sets, we define a general notion of combinatorial objects that includes graphs, hypergraphs, relational structures, codes, permutation groups, tree decompositions, and so on. Our approach allows for a systematic transfer of the techniques that have been developed for isomorphism testing to canonization. We use it to design a canonization algorithm for general combinatorial objects. This result gives new fastest canonization algorithms with an asymptotic running time matching the best known isomorphism algorithm for the following types of objects: hypergraphs, hypergraphs of bounded color class size, permutation groups (up to permutational isomorphism) and codes that are explicitly given (up to code equivalence).


Seems like a good start when it comes to building a new canonization algorithm. An interesting remaining open question is the following:

We ask whether canonization of combinatorial objects can be performed in time $n^{\text{polylog}(|V|)}$ where $n$ is the size of the object. Such a running time is of deep interest for a canonization algorithm for graphs of tree width at most k running in time $|V|^{\text{polylog}(k)}$ which in turn would generalize Babai’s quasipolynomial time bound. However, even for the isomorphism-version of this problem we have no such algorithm yet.

Next follow some other useful quotes:

In practice, a canonization algorithm is often preferable to an isomorphism test, as it allows each graph to be treated separately, rather than having to compare graphs pairwise. For example, when looking up a molecule in a chemical database, we do not wish to compare the molecule individually to every graph that has been stored in the system.

We also describe a technique of computing a canonical representation of ordered groups which in turn allows us to associate a canonical string (encoding) to every ordered object (see Lemma 22). This complements our framework and allows us to use arbitrary deterministic algorithms for ordered objects as a black box in an isomorphism-invariant way.

Some of the techniques we describe here were used in a weaker, non-generic sense in GNSW18 to obtain the fastest known canonization algorithm for graphs of bounded tree width. In fact, tree decompositions, nested tree decompositions, and treelike decompositions can be viewed as combinatorial objects in our framework.

Organization of the Paper. The goal of the paper is to compute canonical labelings for arbitrary objects $\mathcal{X} \in Objects(V)$ formally defined in Section 3. In a bootstrapping manner, we develop can- onization algorithms for objects that are more and more complex. Each algorithm uses the previous ones as a black box.