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.
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
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.
-
1$\begingroup$ A non-paywalled version of the paper is available at people.csail.mit.edu/adam/Papers/tree-depth.pdf. $\endgroup$ Commented Nov 7, 2013 at 16:51
-
3$\begingroup$ 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). $\endgroup$– fraflCommented Nov 11, 2013 at 10:21
-
$\begingroup$ The link to
mpi-inf.mpg.dein 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. $\endgroup$– user67557Commented Feb 19, 2023 at 7:07
$\begingroup$
$\endgroup$
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.
answered Feb 27, 2023 at 10:29
$\begingroup$
$\endgroup$
no FPT algorithm is known. I am wondering whether, under some complexity hypothesis, noone exists.
