6
$\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$
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$
  • 1
    $\begingroup$ A non-paywalled version of the paper is available at people.csail.mit.edu/adam/Papers/tree-depth.pdf. $\endgroup$ – Adam Bouland Nov 7 '13 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 '13 at 10:21
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, privacy policy and cookie policy

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