The Space Complexity of k-Tree Isomorphism (2007)

---

Link: https://link.springer.com/chapter/10.1007/978-3-540-77120-3_71

Abstract: We show that isomorphism testing of k-trees is in the class StUSPACE($\log n$) (strongly unambiguous logspace). This bound follows from a deterministic logspace algorithm that accesses a strongly unambiguous logspace oracle for canonizing $k$-trees. Further we give a logspace canonization algorithm for k-paths.

---

This paper doesn’t give an algorithm directly (though the proof should be enough to make one). The final canonization step is done on a tree representation of the input.

To canonize $k$-trees we use Lindell’s deterministic logspace canonization algorithm for trees which can be made to work for any labeled tree by constructing gadgets for labels. More precisely, consider the algorithm $A$ that on input a $k$-tree $G$ computes the canon of all labeled trees $T(G, B, \theta)$ for all $k$-cliques $B$ in $G$ and all bijections $\theta : B \rightarrow \{1, \dots, k\}$ and picks the lexicographically least among them.