The isomorphism problem for k-trees is complete for logspace (2012)

---

Link: https://www.sciencedirect.com/science/article/pii/S0890540112000879

Abstract: We show that, for $k$ constant, $k$-tree isomorphism can be decided in logarithmic space by giving an $O(k \log n)$ space canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindellʼs tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for $k$-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of $k$-trees. We also show that a variant of our canonical labeling algorithm runs in time $O((k + 1)!n)$, where $n$ is the number of vertices, yielding the fastest known FPT algorithm for $k$-tree isomorphism.

---

This paper contains a clear stepwise algorithm for the canonization of k-trees. Unfortunately there are no labels on the edges and the edges are undirected. The algorithm is an FPT algorithm and makes use of tree decompositions. The final result is as follows:

We proved that the isomorphism and automorphism problems for $k$-trees are complete for logspace, and that canonical labelings of k-trees can be computed in logspace. Further, we described an $O((k + 1)!n)$ time implementation of our canonical labeling algorithm, yielding the fastest known fixed parameter tractable isomorphism algorithm for $k$-trees.

Note that this paper presents a result for k-trees, not partial k-trees which are known to be equivalent to graphs with treewidth $k$. Though the authors express hope that the algorithm might be generalised to partial k-trees in the future.