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

Abstract

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G 1 , G 2 , either concludes that one of these graphs has treewidth at least k, or determines whether G 1 and G 2 are isomorphic. The running time of the algorithm on an n-vertex graph is 2 O(k5 log k) · n 5 , 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 5 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 4 ). 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 1 and G 2 are equal.