7

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.

Kumar
  • 2,044
  • 13
  • 27

3 Answers3

6

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.

Adam Bouland
  • 743
  • 4
  • 10
  • 1
    A non-paywalled version of the paper is available at http://people.csail.mit.edu/adam/Papers/tree-depth.pdf. – Adam Bouland Nov 07 '13 at 16:51
  • 3
    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
  • 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. –  Feb 19 '23 at 07:07
3

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.

Christian Komusiewicz
  • 1,802
  • 13
  • 21
2

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

M. kanté
  • 1,046
  • 7
  • 10