Faster algorithms speed up 3 and 4 color graph solutions
Faster Exact Algorithms for 3- and 4-Coloring: Deterministic Improvements and Further Randomized Speedups
Data Structures and Algorithms
Summary
The paper improves how quickly computers can solve problems where items must be colored using only 3 or 4 colors so that no connected items share the same color. The authors found ways to make these solutions faster than before, both with guaranteed methods and with some random guessing to speed things up even more. This is notable because before, only problems with more colors had clear speedups from randomness. Their work suggests that random guesswork might help solve these coloring puzzles much faster.
What this means in practice
- •For software engineers: Design graph coloring algorithms that run faster in scheduling and resource allocation problems using the improved exact methods for 3- and 4-coloring.
- •For network analysts: Analyze network structures more efficiently by applying faster 3- and 4-coloring algorithms to detect conflicts and optimize channel assignments.
Authors
Ryosuke Yamano, Tetsuo Shibuya
Abstract
We study exact exponential-time algorithms for 3- and 4-coloring. For 3-coloring, the best previously published running-time bound is $O^*(1.3289^n)$, due to Eppstein (SODA 2001). We improve this bound to $O^*(1.3204^n)$ deterministically and $O^*(1.3159^n)$ using randomization. For 4-coloring, the best previously known running-time bound is $O^*(1.7159^n)$, due to Wu, Gu, Jiang, Shao, and Xu (ESA 2024). We improve this bound to $O^*(1.6975^n)$ deterministically and $O^*(1.6933^n)$ using randomization. Our algorithms for both problems combine constraint satisfaction algorithms with dynamic programming over tree and path decompositions, exploiting their complementary strengths on different graph structures. For 6-coloring, the best published randomized running-time bound is exponentially smaller than the best published deterministic bound. For 3- and 4-coloring, however, no such improvement through randomization was previously known. To the best of our knowledge, our results provide the first randomized running-time bounds for these two problems that exponentially improve upon the best previously published deterministic bounds. This raises the question of whether randomization offers an inherent exponential advantage for 3- and 4-coloring.