Graph Isomorphism FPT by Clique-Width

Open Question: FPT Algorithm for Graph Isomorphism Parameterized by Clique-Width · arXiv:1811.12252

arXiv Question medium confidence— first stated 2019-09-03

Authors: Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron

Status open high confidence

As of 2026 it remains open whether Graph Isomorphism admits an FPT algorithm parameterized by clique-width; the best known result is XP membership due to Grohe and Schweitzer. A 2025 IPEC paper (Blažej, Jana, Ramanujan, Strulo) proves FPT for the new intermediate parameter cograph-modular-treewidth, which lies strictly between treewidth and clique-width, but explicitly confirms that the FPT status for clique-width itself is still open. No W[1]-hardness evidence for clique-width parameterization has been established.

Cited literature (1)

partial Bridging Treewidth and Clique-Width via Cograph-Modular-Treewidth (2025)

Václav Blažej, Satyabrata Jana, M. S. Ramanujan, Peter Strulo · 20th International Symposium on Parameterized and Exact Computation (IPEC 2025), LIPIcs · doi:10.4230/LIPIcs.IPEC.2025.18

Introduces cograph-modular-treewidth (strictly between treewidth and clique-width) and proves Graph Isomorphism is FPT for this parameter, while noting the FPT status for clique-width remains open.

Reviewer notes. The FPT status of Graph Isomorphism parameterized by clique-width is one of the central open problems in parameterized complexity. No internal references were supplied. The IPEC 2025 paper by Blažej et al. is the closest recent progress, establishing FPT for a strictly intermediate parameter (cograph-modular-treewidth) that does not subsume the full clique-width case.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Question. Whether an FPT algorithm exists for Graph Isomorphism when parameterized by clique-width is still open.

Context

Lokshtanov et al. [23] gave an FPT algorithm parameterized by treewidth, and Grohe and Schweitzer [20] proved XP membership parameterized by clique-width (i.e., polynomial-time solvability for each fixed clique-width). The question of whether the parameter clique-width admits an FPT algorithm remains unresolved.

Notes. Stated as an existing open problem in the introduction without attribution to specific authors; not a formally labelled environment. PDF source — math notation appears clean for this item.

Source paper

Graph Isomorphism for $(H_1,H_2)$-free Graphs: An Almost Complete Dichotomy
Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron · 2019-09-03
https://arxiv.org/abs/1811.12252 PDF source