Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Radu-Cristian  Curticapean; Andreas Björklund; Thore  Husfeldt; Petteri Kaski; Kevin Pratt

doi:10.1137/1.9781611978322.91

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Radu-Cristian Curticapean
, Andreas Björklund
, Thore Husfeldt
, Petteri Kaski
, Kevin Pratt

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

Abstract

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.99982n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2n 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 2n 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.

Original language	English
Title of host publication	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages	15
Publication date	1 Jan 2025
Pages	2804-2818
ISBN (Print)	9798331312008
DOIs	https://doi.org/10.1137/1.9781611978322.91
Publication status	Published - 1 Jan 2025
Event	Symposium on Discrete Algorithms - New Orleans, United States Duration: 12 Jan 2025 → 15 Jan 2025 https://www.siam.org/conferences-events/past-event-archive/soda25/

Symposium

Symposium	Symposium on Discrete Algorithms
Country/Territory	United States
City	New Orleans
Period	12/01/2025 → 15/01/2025
Internet address	https://www.siam.org/conferences-events/past-event-archive/soda25/

Keywords

Graph coloring
Tensor rank
Asymptotic rank conjecture
Deterministic algorithms
Three-way partitioning

Access to Document

10.1137/1.9781611978322.91

https://epubs.siam.org/doi/epdf/10.1137/1.9781611978322.91

CountHom: Counting (with) homomorphisms
Curticapean, R.-C. (PI) & Seppelt, T. F. (Collaborator)
European Commission
01/04/2023 → 31/03/2028
Project: Research

Cite this

@inproceedings{fc3c743efbe04b6f9ee4edc07372793a,

title = "Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture",

abstract = "In this paper we further explore the recently discovered connection by Bj{\"o}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.99982n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2n poly(n ) time algorithm for chromatic number by Bj{\"o}rklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to 2n 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{\textquoteright}s tensor-based algorithm for balanced three-way partitioning to the unbalanced case.",

keywords = "Graph coloring, Tensor rank, Asymptotic rank conjecture, Deterministic algorithms, Three-way partitioning",

author = "Radu-Cristian Curticapean and Andreas Bj{\"o}rklund and Thore Husfeldt and Petteri Kaski and Kevin Pratt",

year = "2025",

month = jan,

day = "1",

doi = "10.1137/1.9781611978322.91",

language = "English",

isbn = "9798331312008",

pages = "2804--2818",

booktitle = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

note = "Symposium on Discrete Algorithms, SODA ; Conference date: 12-01-2025 Through 15-01-2025",

url = "https://www.siam.org/conferences-events/past-event-archive/soda25/",

}

TY - GEN

T1 - Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

AU - Curticapean, Radu-Cristian

AU - Björklund, Andreas

AU - Husfeldt, Thore

AU - Kaski, Petteri

AU - Pratt, Kevin

PY - 2025/1/1

Y1 - 2025/1/1

N2 - 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.99982n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2n 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 2n 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.

AB - 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.99982n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2n 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 2n 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.

KW - Graph coloring

KW - Tensor rank

KW - Asymptotic rank conjecture

KW - Deterministic algorithms

KW - Three-way partitioning

U2 - 10.1137/1.9781611978322.91

DO - 10.1137/1.9781611978322.91

M3 - Article in proceedings

SN - 9798331312008

SP - 2804

EP - 2818

BT - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - Symposium on Discrete Algorithms

Y2 - 12 January 2025 through 15 January 2025

ER -

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

Abstract

Symposium

Keywords

Access to Document

Fingerprint

Projects

CountHom: Counting (with) homomorphisms

Cite this