The fastest known classical algorithm deciding the @math -colorability of @math -vertex graph requires running time @math for @math . In this work, we present an exponential-space quantum algorithm computing the chromatic number with running time @math using quantum random access memory (QRAM). Our approach is based on 's quantum dynamic programming with applications of Grover's search to branching algorithms. We also present a polynomial-space quantum algorithm not using QRAM for the graph @math -coloring problem with running time @math . In the polynomial-space quantum algorithm, we essentially show @math -time classical algorithms that can be improved quadratically by Grover's search.
In 2006, Bj "orklund and Husfeldt, and Koivisto showed an exponential-space @math -time algorithm for the chromatic number problem on the RAM model @cite_5 , @cite_3 . These algorithms are based on the inclusion--exclusion principle. They also showed that if there is a polynomial-space @math -time algorithm counting the number of independent sets, then there is a polynomial-space @math -time algorithm computing the chromatic number @cite_5 , @cite_7 . Since the fastest known polynomial-space algorithm computes the number of independent sets with running time @math @cite_15 , there is a polynomial-space @math -time algorithm computing the chromatic number.
@cite_5 @cite_15 @cite_7 @cite_3
2163938320 2962886649 2074359677 2002425091
Given a set U with n elements and a family of subsets S 2^U we show how to count the number of k-partitions S_1 ? ? ? S_k = U into subsets S_i S in time 2^ n n^ O(1) . The only assumption on S is that it can be enumerated in time 2^ n n^ O(1) . In effect we get exact algorithms in time 2^ n n^ O(1) for several well-studied partition problems including Domatic Number, Chromatic Number, Bounded Component Spanning Forest, Partition into Hamiltonian Subgraphs, and Bin Packing. If only polynomial space is available, our algorithms run in time 3^ n n^ O(1) if membership in S can be decided in polynomial time. For Chromatic Number, we present a version that runs in time O(2.2461^n ) and polynomial space. For Domatic Number, we present a version that runs in time O(2.8718^n ). Finally, we present a family of polynomial space approximation algorithms that find a number between ( G ) and ( 1 + ) ( G ) in time O(1.2209^n + 2.2461^ e^ - n ). We present a polynomial-space algorithm that computes the number of independent sets of any input graph in time (O(1.1389^n) ) for graphs with maximum degree 3 and in time (O(1.2356^n) ) for general graphs, where n is the number of vertices. Together with the inclusion-exclusion approach of Bjorklund, Husfeldt, and Koivisto [SIAM J. Comput. 2009], this leads to a faster polynomial-space algorithm for the graph coloring problem with running time (O(2.2356^n) ). As a byproduct, we also obtain an exponential-space (O(1.2330^n) ) time algorithm for counting independent sets. Given a set @math with @math elements and a family @math of subsets, we show how to partition @math into @math such subsets in @math time. We also consider variations of this problem where the subsets may overlap or are weighted, and we solve the decision, counting, summation, and optimization versions of these problems. Our algorithms are based on the principle of inclusion-exclusion and the zeta transform. In effect we get exact algorithms in @math time for several well-studied partition problems including domatic number, chromatic number, maximum @math -cut, bin packing, list coloring, and the chromatic polynomial. We also have applications to Bayesian learning with decision graphs and to model-based data clustering. If only polynomial space is available, our algorithms run in time @math if membership in @math can be decided in polynomial time. We solve chromatic number in @math time and domatic number in @math time. Finally, we present a family of polynomial space approximation algorithms that find a number between @math and @math in time @math . We use the principle of inclusion and exclusion, combined with polynomial time segmentation and fast Mobius transform, to solve the generic problem of summing or optimizing over the partitions of n elements into a given number of weighted subsets. This problem subsumes various classical graph partitioning problems, such as graph coloring, domatic partitioning, and MAX k-CUT, as well as machine learning problems like decision graph learning and model-based data clustering. Our algorithm runs in O*(2^n ) time, thus substantially improving on the usual O*(3^n )-time dynamic programming algorithm; the notation O* suppresses factors polynomial in n. This result improves, e.g., Byskov?s recent record for graph coloring from O*(2.4023^n ) to O*(2^n ). We note that twenty five years ago, R. M. Karp used inclusion--exclusion in a similar fashion to reduce the space requirement of the usual dynamic programming algorithms from exponential to polynomial.