DROPS

Document

DOI: 10.4230/LIPIcs.WG.2026.26

Weisfeiler-Leman on Graphs of Small Twin-Width

Authors: Irene Heinrich, Moritz Lichter, Klara Pakhomenko, and Simon Raßmann

Published in: LIPIcs, Volume 376, 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)

Abstract

Twin-width is a graph parameter introduced in the context of first-order model checking, and has since become a central parameter in algorithmic graph theory. While many algorithmic problems become easier on arbitrary classes of bounded twin-width, graph isomorphism on graphs of twin-width 4 and above is as hard as the general isomorphism problem. For each positive integer k, the k-dimensional Weisfeiler-Leman algorithm is an iterative color refinement algorithm that encodes structural similarities and serves as a fundamental tool for distinguishing non-isomorphic graphs. We show that the graph isomorphism problem for graphs of twin-width 1 can be solved by the 3-dimensional Weisfeiler-Leman algorithm, while there is no fixed k such that the k-dimensional Weisfeiler-Leman algorithm solves the graph isomorphism problem for graphs of twin-width 4. Moreover, we prove the conjecture of Bergougnoux, Gajarský, Guspiel, Hlinený, Pokrývka, and Sokolowski (ISAAC 2023) that stable graphs of twin-width 2 have bounded rank-width. This implies that isomorphism of these graphs is solved by a fixed dimension of the Weisfeiler-Leman algorithm.

Cite as

Irene Heinrich, Moritz Lichter, Klara Pakhomenko, and Simon Raßmann. Weisfeiler-Leman on Graphs of Small Twin-Width. In 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 376, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{heinrich_et_al:LIPIcs.WG.2026.26,
  author =	{Heinrich, Irene and Lichter, Moritz and Pakhomenko, Klara and Ra{\ss}mann, Simon},
  title =	{{Weisfeiler-Leman on Graphs of Small Twin-Width}},
  booktitle =	{52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2026)},
  pages =	{26:1--26:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-430-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{376},
  editor =	{Goedgebeur, Jan and Rz\k{a}\.{z}ewski, Pawe{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WG.2026.26},
  URN =		{urn:nbn:de:0030-drops-261929},
  doi =		{10.4230/LIPIcs.WG.2026.26},
  annote =	{Keywords: twin-width, Weisfeiler-Leman algorithm, canonization, half-graph, rank-width}
}

Search Results

Documents authored by Pakhomenko, Klara

Weisfeiler-Leman on Graphs of Small Twin-Width

Abstract

Cite as

Thanks for your feedback!

Could not send message