Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912815269281792 |
|---|---|
| author | Grohe, Martin Lichter, Moritz Neuen, Daniel Schweitzer, Pascal |
| author_facet | Grohe, Martin Lichter, Moritz Neuen, Daniel Schweitzer, Pascal |
| contents | The $k$-dimensional Weisfeiler-Leman ($k$-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai's quasipolynomial time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning.
The algorithm iteratively computes a coloring of the $k$-tuples of vertices of a graph. Since Fürer's linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for $k$-WL on graphs. We answer this question affirmatively, establishing an $Ω(n^{k/2})$-lower bound for all $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_11970 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements Grohe, Martin Lichter, Moritz Neuen, Daniel Schweitzer, Pascal Discrete Mathematics Data Structures and Algorithms Logic in Computer Science The $k$-dimensional Weisfeiler-Leman ($k$-WL) algorithm is a simple combinatorial algorithm that was originally designed as a graph isomorphism heuristic. It naturally finds applications in Babai's quasipolynomial time isomorphism algorithm, practical isomorphism solvers, and algebraic graph theory. However, it also has surprising connections to other areas such as logic, proof complexity, combinatorial optimization, and machine learning. The algorithm iteratively computes a coloring of the $k$-tuples of vertices of a graph. Since Fürer's linear lower bound [ICALP 2001], it has been an open question whether there is a super-linear lower bound for the iteration number for $k$-WL on graphs. We answer this question affirmatively, establishing an $Ω(n^{k/2})$-lower bound for all $k$. |
| title | Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements |
| topic | Discrete Mathematics Data Structures and Algorithms Logic in Computer Science |
| url | https://arxiv.org/abs/2308.11970 |