Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866913599815942144 |
|---|---|
| author | Björklund, Andreas Curticapean, Radu Husfeldt, Thore Kaski, Petteri Pratt, Kevin |
| author_facet | Björklund, Andreas Curticapean, Radu Husfeldt, Thore Kaski, Petteri Pratt, Kevin |
| contents | In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an $n$-vertex graph can be computed deterministically in $O(1.99982^n)$ time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the $2^n\operatorname{poly}(n)$ time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to $2^n$ time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture. Our technique is a combination of earlier algorithms for detecting $k$-colorings for small $k$ and enumerating $k$-colorable subgraphs, with an extension and derandomisation of Pratt's tensor-based algorithm for balanced three-way partitioning to the unbalanced case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04987 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture Björklund, Andreas Curticapean, Radu Husfeldt, Thore Kaski, Petteri Pratt, Kevin Data Structures and Algorithms In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an $n$-vertex graph can be computed deterministically in $O(1.99982^n)$ time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the $2^n\operatorname{poly}(n)$ time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to $2^n$ time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture. Our technique is a combination of earlier algorithms for detecting $k$-colorings for small $k$ and enumerating $k$-colorable subgraphs, with an extension and derandomisation of Pratt's tensor-based algorithm for balanced three-way partitioning to the unbalanced case. |
| title | Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.04987 |