A space improved algorithm for chromatic number

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ö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 9 n 25 ) = O ( 1. 2835 n ).

Authors

• Pu Wu
• Huanyu Gu
• Huiqin Jiang
• Zehui Shao
• Jin Xu Pazhou Lab, Guangzhou South China University of Technology

Keywords

• Graph coloring
• Graph algorithms
• Exact algorithms
• 05C15
• 05C85
• 68Q25