7
$\begingroup$

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.

$\endgroup$

3 Answers 3

6
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ A non-paywalled version of the paper is available at people.csail.mit.edu/adam/Papers/tree-depth.pdf. $\endgroup$ 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$
    – frafl
    Nov 11, 2013 at 10:21
  • $\begingroup$ 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. $\endgroup$
    – user67557
    Feb 19, 2023 at 7:07
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.