Weisfeiler-Leman on graphs of small twin-width
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915719275347968 |
|---|---|
| author | Heinrich, Irene Lichter, Moritz Pakhomenko, Klara Raßmann, Simon |
| author_facet | Heinrich, Irene Lichter, Moritz Pakhomenko, Klara Raßmann, Simon |
| contents | 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 number $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 purely combinatorial 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 that stable graphs of twin-width 2 have bounded rank-width. This in particular implies that isomorphism of these graphs can be decided by a fixed dimension of the Weisfeiler-Leman algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_05892 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Weisfeiler-Leman on graphs of small twin-width Heinrich, Irene Lichter, Moritz Pakhomenko, Klara Raßmann, Simon Combinatorics Discrete Mathematics Data Structures and Algorithms G.2.2; F.4.1 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 number $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 purely combinatorial 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 that stable graphs of twin-width 2 have bounded rank-width. This in particular implies that isomorphism of these graphs can be decided by a fixed dimension of the Weisfeiler-Leman algorithm. |
| title | Weisfeiler-Leman on graphs of small twin-width |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms G.2.2; F.4.1 |
| url | https://arxiv.org/abs/2601.05892 |