Chromatic number in 1.9999^n time? Fast deterministic set partitioning under the asymptotic rank conjecture
arxiv(2024)
摘要
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^npoly(n)
time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto
[SICOMP 2009].
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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要