Wednesday 25 February 2015
4pm - 5pm, OLD 1.27, Old Building, Houghton Street
Abstract
We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G1,G2, either concludes one of these graphs has treewidth at least k, or determines whether G1 and G2 are isomorphic. The running time of the algorithm on an n-vertex graph is 2^O(k^5 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^O(k^5 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 G1 and G2 are equal.
Based on joint work with Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh.