Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G₁, G₂, either concludes that one of these graphs has treewidth at least k, or determines whether G₁ and G₂ are isomorphic. The running time of the algorithm on an n-vertex graph is 2^{O(k5 log k)} · n⁵, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in 2^{OO(k5 log k)} · n⁵ time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k, or finds an isomorphism-invariant construction term - an algebraic expression that encodes G together with a tree decomposition of G of width O(k⁴). Hence, a canonical graph isomorphic to G can be constructed by simply evaluating the obtained construction term, while the isomorphism test reduces to verifying whether the computed construction terms for G₁ and G₂ are equal.