A space improved algorithm for chromatic number

Pu Wu

doi:10.1016/j.tcs.2025.115584

2025-11-01

PRE

DOI：10.1016/j.tcs.2025.115584

原文链接

原文求助

摘要

En 中文

We investigate the chromatic number problem, a classic NP-complete problem identified by Karp among his 21 seminal problems. The chromatic number of a graph G is the smallest integer k such that each vertex of G can be assigned one of k colors, with no two adjacent vertices assigned the same color. The chromatic number problem requires determining this minimum k for a given graph G with n vertices. The questions of whether an algorithm for the chromatic number problem with time complexity O*(a(n)), where a < 2, exists, and whether an algorithm for the chromatic number problem with time complexity O*(2(n)) and polynomial space exists, both remain unresolved. The fastest known algorithm for the chromatic number problem was proposed by Bj & ouml;rklund, Husfeldt, and Koivisto (FOCS 2006), with the time and space complexity of O*(2(n)). Subsequently, in their follow-up work (ICALP 2010), the space complexity is reduced to O(1.2916(n)). In this work, we present an improved algorithm for the chromatic number problem. Building on prior research, our approach leverages algebraic methods, specifically the generating functions and the discrete Fourier transform. Our main contribution demonstrates that by utilizing these algebraic techniques, certain structural properties of graphs can be exploited to reduce space complexity, while preserving the best-known time complexity of O*(2(n)). Specifically, our algorithm achieves a time complexity of O*(2(n)) and a space complexity of O*(2(9n/25) ) = O(1.2835(n)).

Keyword:

Graph coloring

Graph algorithms

Exact algorithms