Home > Department of Mathematics > Seminars > OR Seminar Series > Academic year 2014-15 > Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth
How to contact us

 

LSE 10 logo master_6


Department of Management
London School of Economics and Political Science
Houghton Street

London WC2A 2AE

  

Enquiries: dom.events@lse.ac.uk 

  

Follow us online

Facebook-Square-38x38Twitter-square-38x38Youtube-square-38x38

 

Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth

Wednesday 25 February 2015
Daniel Lokshtanov 

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.

Share:Facebook|Twitter|LinkedIn|
Daniel Lokshtanov