# FPT algorithm for Partial k-tree Isomorphism

H.L. Bodlander in Polynomial algorithms for graph isomorphism and chromatic index on partial $k$-trees given a polynomial time algorithm for graph isomorphism when $k$ is constant.

Is there any FPT algorithm for partial $k$-tree isomorphism.

As M. kanté pointed out, it's open whether or not graph isomorphism is FPT when parameterized by tree-width. Furthermore, I don't believe there is any complexity-theoretic barrier to creating an FPT algorithm in this case.

For a survey of what's known about the fixed-parameter tractability of graph isomorphism, see the introduction of my paper with Anuj Dawar and Eryk Kopczyński here. In the paper we show graph isomorphism is FPT in the tree-depth of a graph, which is a necessary (but not sufficient) condition for graph isomorphism to be FPT in tree-width.

• A non-paywalled version of the paper is available at people.csail.mit.edu/adam/Papers/tree-depth.pdf. Nov 7, 2013 at 16:51
• Please note, that the problem is even open for the path / tree distance width and only solved for the rooted tree distance width and some other restrictions (e.g. root sets with c components). The feedback vertex number is another parameter such that $tw\leq f(fvs)$ and for which GI is in FPT (see here, but canonization is open AFAIK). Nov 11, 2013 at 10:21
• The link to mpi-inf.mpg.de in a comment above seems to be broken; it's probably meant to point to the following article: Kratsch, Stefan; Schweitzer, Pascal, Isomorphism for graphs of bounded feedback vertex set number. In: Kaplan, H. (eds) Algorithm Theory - SWAT 2010. SWAT 2010. Lecture Notes in Computer Science, vol 6139, Springer: Berlin, Heidelberg., pp. 81–92 (2010). Zbl 1284.05296.
– user67557
Feb 19 at 7:07

In the meantime, it was shown that Graph Isomorphism is FPT with respect to the treewidth of the graphs.

Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh: Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, SIAM J. Comput. 46(1): 161-189 (2017), https://doi.org/10.1137/140999980.

no FPT algorithm is known. I am wondering whether, under some complexity hypothesis, noone exists.