Logarithmic Weisfeiler--Leman and Treewidth
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913328310255616 |
|---|---|
| author | Levet, Michael Rombach, Puck Sieger, Nicholas |
| author_facet | Levet, Michael Rombach, Puck Sieger, Nicholas |
| contents | In this paper, we show that the $(3k+4)$-dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth $k$ in $O(\log n)$ rounds. This improves the result of Grohe & Verbitsky (ICALP 2006), who previously established the analogous result for $(4k+3)$-dimensional Weisfeiler--Leman. In light of the equivalence between Weisfeiler--Leman and the logic $\textsf{FO} + \textsf{C}$ (Cai, Fürer, & Immerman, Combinatorica 1992), we obtain an improvement in the descriptive complexity for graphs of treewidth $k$. Precisely, if $G$ is a graph of treewidth $k$, then there exists a $(3k+5)$-variable formula $φ$ in $\textsf{FO} + \textsf{C}$ with quantifier depth $O(\log n)$ that identifies $G$ up to isomorphism. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_07985 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Logarithmic Weisfeiler--Leman and Treewidth Levet, Michael Rombach, Puck Sieger, Nicholas Data Structures and Algorithms Computational Complexity Logic in Computer Science Combinatorics 05C60, 68Q19, 68Q25, 68R10 F.2.2; G.2.2 In this paper, we show that the $(3k+4)$-dimensional Weisfeiler--Leman algorithm can identify graphs of treewidth $k$ in $O(\log n)$ rounds. This improves the result of Grohe & Verbitsky (ICALP 2006), who previously established the analogous result for $(4k+3)$-dimensional Weisfeiler--Leman. In light of the equivalence between Weisfeiler--Leman and the logic $\textsf{FO} + \textsf{C}$ (Cai, Fürer, & Immerman, Combinatorica 1992), we obtain an improvement in the descriptive complexity for graphs of treewidth $k$. Precisely, if $G$ is a graph of treewidth $k$, then there exists a $(3k+5)$-variable formula $φ$ in $\textsf{FO} + \textsf{C}$ with quantifier depth $O(\log n)$ that identifies $G$ up to isomorphism. |
| title | Logarithmic Weisfeiler--Leman and Treewidth |
| topic | Data Structures and Algorithms Computational Complexity Logic in Computer Science Combinatorics 05C60, 68Q19, 68Q25, 68R10 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2303.07985 |