# 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. – Adam Bouland Nov 7 '13 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). – frafl Nov 11 '13 at 10:21

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