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.
Beigel and Eppstein showed an efficient algorithm for the graph 3-coloring problem with running time @math @cite_1 . Byskov showed reduction algorithms from the graph @math -coloring problem to the graph 3-coloring problem @cite_9 . By using Beigel and Eppstein's graph 3-coloring algorithm, Byskov showed classical algorithms for the graph 4-, 5- and 6-coloring problems with running time @math , @math and @math , respectively. showed an algorithm for the graph 4-coloring problem with running time @math by using the path decomposition @cite_11 .
@cite_9 @cite_1 @cite_11
2122639972 1533811829 1598159863
We give tight upper bounds on the number of maximal independent sets of size k (and at least k and at most k) in graphs with n vertices. As an application of the proof, we construct improved algorithms for graph colouring and computing the chromatic number of a graph. We consider worst case time bounds for several NP-complete problems, based on a constraint satisfaction (CSP) formulation of these problems: (a, b)-CSP instances consist of a set of variables, each with up to a possible values, and constraints disallowing certain b-tuples of variable values; a problem is solved by assigning values to all variables satisfying all constraints, or by showing that no such assignment exist. 3-SAT is equivalent to (2, 3)-CSP while 3-coloring and various related problems are special cases of (3, 2)-CSP; there is also a natural duality transformation from (a, b)-CSP to (b, a)-CSP. We show that n-variable (3, 2)-CSP instances can be solved in time O(1.3645n), that satisfying assignments to (d, 2)-CSP instances can be found in randomized expected time O((0.4518d)n); that 3-coloring of n-vertex graphs can be solved in time O(1.3289n); that 3-list-coloring of n-vertex graphs can be solved in time O(1.3645n); that 3-edge-coloring of n-vertex graphs can be solved in time O(2n 2), and that 3-satisfiability of a formula with t 3-clauses can be solved in time O(nO(1) + 1.3645t). We introduce a generic algorithmic technique and apply it on decision and counting versions of graph coloring. Our approach is based on the following idea: either a graph has nice (from the algorithmic point of view) properties which allow a simple recursive procedure to find the solution fast, or the pathwidth of the graph is small, which in turn can be used to find the solution by dynamic programming. By making use of this technique we obtain the fastest known exact algorithms - running in time O(1.7272n) for deciding if a graph is 4-colorable and - running in time O(1.6262n) and O(1.9464n) for counting the number of k-colorings for k = 3 and 4 respectively.