<p>In the meantime, it was shown that Graph Isomorphism is FPT with respect to the treewidth of the graphs.</p>
<p>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), <a href="https://doi.org/10.1137/140999980" rel="nofollow noreferrer">https://doi.org/10.1137/140999980</a>.</p>

CC BY-SA 4.0
2023-02-27T10:29:31.243Z
2023-02-27T10:29:31.243Z
Christian Komusiewicz
<p>no FPT algorithm is known. I am wondering whether, under some complexity hypothesis, noone exists. </p>

CC BY-SA 3.0
2013-11-07T08:56:10.577Z
2013-11-07T08:56:10.577Z
M. kanté
<p>As <a href="https://cstheory.stackexchange.com/a/19701">M. kanté</a> 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.</p>
<p>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 <a href="https://doi.org/10.1007/978-3-642-33293-7_21" rel="nofollow noreferrer" title="Bouland, A., Dawar, A., Kopczyński, E. (2012). On Tractable Parameterizations of Graph Isomorphism. In: Thilikos, D.M., Woeginger, G.J. (eds) Parameterized and Exact Computation. IPEC 2012. Lecture Notes in Computer Science, vol 7535. Springer, Berlin, Heidelberg.">here</a>. In the paper we show graph isomorphism is FPT in the tree-<em>depth</em> of a graph, which is a necessary (but not sufficient) condition for graph isomorphism to be FPT in tree-width.</p>

CC BY-SA 3.0
2013-11-07T16:51:50.140Z
A non-paywalled version of the paper is available at http://people.csail.mit.edu/adam/Papers/tree-depth.pdf.
Adam Bouland
CC BY-SA 3.0
2013-11-11T10:21:17.890Z
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](http://www.mpi-inf.mpg.de/~pascal/docs/feedback_griso_KratschSchw.pdf), but canonization is open AFAIK).
frafl
CC BY-SA 4.0
2013-11-07T16:25:57.847Z
2023-02-27T09:45:11.060Z
2023-02-27T09:45:11.060Z
Adam Bouland
<p>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.</p>

<p>Is there any FPT algorithm for partial $k$-tree isomorphism.</p>

<reference-request><graph-isomorphism>
FPT algorithm for Partial k-tree Isomorphism
Kumar
# FPT algorithm for Partial k-tree Isomorphism

(Asked by: username_0 on 2013-11-07)

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.

**Tags:** reference-request, graph-isomorphism


---

## 3 answers

### Answer by username_3 on 2013-11-07. Score: 6 | Accepted answer

As [username_2](https://cstheory.stackexchange.com/a/19701) 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](https://doi.org/10.1007/978-3-642-33293-7_21 "Bouland, A., Dawar, A., Kopczyński, E. (2012). On Tractable Parameterizations of Graph Isomorphism. In: Thilikos, D.M., Woeginger, G.J. (eds) Parameterized and Exact Computation. IPEC 2012. Lecture Notes in Computer Science, vol 7535. Springer, Berlin, Heidelberg."). 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.

> **Comments:**
> **username_3**: A non-paywalled version of the paper is available at http://people.csail.mit.edu/adam/Papers/tree-depth.pdf.  
> **username_4**: 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](http://www.mpi-inf.mpg.de/~pascal/docs/feedback_griso_KratschSchw.pdf), but canonization is open AFAIK).  

---

### Answer by username_1 on 2023-02-27. Score: 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>.


---

### Answer by username_2 on 2013-11-07. Score: 2

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


---

