An Improved Isomorphism Test for Bounded-tree-width Graphs (2020)

---

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

Abstract: We give a new FPT algorithm testing isomorphism of $n$-vertex graphs of tree-width $k$ in time $2^{k \cdot \text{polylog}(k)}n^3$, improving the FPT algorithm due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh (FOCS 2014), which runs in time $2^{O(k^5 \cdot \log k)}n^5$. Based on an improved version of the isomorphism-invariant graph decomposition technique introduced by Lokshtanov et al., we prove restrictions on the structure of the automorphism groups of graphs of tree-width k. Our algorithm then makes heavy use of the group theoretic techniques introduced by Luks (JCSS 1982) in his isomorphism test for bounded degree graphs and Babai (STOC 2016) in his quasipolynomial isomorphism test. In fact, we even use Babai’s algorithm as a black box in one place. We also give a second algorithm that, at the price of a slightly worse running time $2^{O(k^2 \cdot \log k)}n^3$, avoids the use of Babai’s algorithm and, more importantly, has the additional benefit that it can also be used as a canonization algorithm.

---

This paper proposes an interesting FTP algorithm for graph isomorphism testing and also a slightly modified algorithm for canonization. Unfortunately, the content seems quite complicated and edge labels and directed graphs do not appear to be supported. From the following quote and a mention in the paper on canonization algorithm design this does seem to be a state of the art algorithm for canonization up to this point in time. Judging by citations in Google scholar this algorithm is still the state of the art for the general case. However, some new algorithms with extra requirements on the input graph exist.

In this section, we adapt our techniques to obtain an algorithm that computes a canonical form for a given graph of tree-width at most k. Since the isomorphism test for graphs of bounded degree given in [13] can not be used for canonization purposes, our canonization algorithm has a slightly worse running time. However, our canonization algorithm still significantly improves on the previous best due to Lokshtanov, Pilipczuk, Pilipczuk, and Saurabh [18].

The following was another interesting property from the paper:

A graph G is $k$-degenerate if every subgraph of G has a vertex with degree at most $k$. It is well known that every graph of tree-width $k$ is $k$-degenerate. In particular, for a graph $G$ of tree-width $k$ it holds that $|E(G)| \leq k \cdot |V(G)|$.