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
2751147784 2097520314 2025904765 2036660814
Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this area. Combinatorial algorithms are often simpler than their algebraic counterparts. Moreover, in many cases, combinatorial algorithms and proofs provide additional understanding of studied problems. In this paper we initiate the study of combinatorial algorithms for Distributed Graph Coloring problems. In a distributed setting a communication network is modeled by a graph (G=(V,E) ) of maximum degree ( ). The vertices of (G ) host the processors, and communication is performed over the edges of (G ). The goal of distributed vertex coloring is to color (V ) with (( + 1) ) colors such that any two neighbors are colored with distinct colors. Currently, efficient algorithms for vertex coloring that require (O( + ^* n) ) time are based on the algebraic algorithm of Linial (SIAM J Comput 21(1):193–201, 1992) that employs set-systems. The best currently-known combinatorial set-system free algorithm, due to (SIAM J Discret Math 1(4):434–446, 1988), requires (O( ^2+ ^*n) ) time. We significantly improve over this by devising a combinatorial (( + 1) )-coloring algorithm that runs in (O( + ^* n) ) time. This exactly matches the running time of the best-known algebraic algorithm. In addition, we devise a tradeoff for computing (O( t) )-coloring in (O( t + ^* n) ) time, for almost the entire range (1 < t < ). We also compute a Maximal Independent Set in (O( + ^* n) ) time on general graphs, and in (O( n n) ) time on graphs of bounded arboricity. Prior to our work, these results could be only achieved using algebraic techniques. We believe that our algorithms are more suitable for real-life networks with limited resources, such as sensor networks. Given a 3-colorable graph G together with two proper vertex 3-colorings α and β of G, consider the following question: is it possible to transform α into β by recoloring vertices of G one at a time, making sure that all intermediate colorings are proper 3-colorings? We prove that this question is answerable in polynomial time. We do so by characterizing the instances G, α, β where the transformation is possible; the proof of this characterization is via an algorithm that either finds a sequence of recolorings between α and β, or exhibits a structure which proves that no such sequence exists. In the case that a sequence of recolorings does exist, the algorithm uses O(|V(G)|2) recoloring steps and in many cases returns a shortest sequence of recolorings. We also exhibit a class of instances G, α, β that require Ω(|V(G)|2) recoloring steps. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 69-82, 2011 © 2011 Wiley Periodicals, Inc. Graph coloring problems, in which one would like to color the vertices of a given graph with a small number of colors so that no two adjacent vertices receive the same color, arise in many applications, including various scheduling and partitioning problems. In this paper the complexity and performance of algorithms which construct such colorings are investigated. For a graph G , let k( G ) denote the minimum possible number of colors required to color G and, for any graph coloring algorithm A , let A ( G ) denote the number of colors used by A when applied to G . Since the graph coloring problem is known to be “NP-complete,” it is considered unlikely that any efficient algorithm can guarantee A ( G ) = k( G ) for all input graphs. In this paper it is proved that even coming close to khgr;( G ) with a fast algorithm is hard. Specifically, it is shown that if for some constant r d there exists a polynomial-time algorithm A which guarantees A ( G ) ≤ r ·k( G ) + d , then there also exists a polynomial-time algorithm A which guarantees A ( G ) = k( G ). The problem of coloring a graph with the minimum number of colorsis well known to be NP-hard, even restricted to k -colorable graphs for constant k ≥ 3. This paper explores theapproximation problem of coloring k -colorable graphs with as fewadditional colors as possible in polynomial time, with special focus onthe case of k = 3. The previous best upper bound on the number of colors needed forcoloring 3-colorable n -vertex graphsin polynomial time was o n log n colors by Berger and Rompel, improving a bound of o n colors by Wigderson. This paper presents an algorithmto color any 3-colorable graph with o n3 8 polylog n colors, thus breaking an“ O((n 1 2-o(1) ) barrier”. The algorithm given here is based on examiningsecond-order neighborhoods of vertices, rather than just immediateneighborhoods of vertices as in previous approaches. We extend ourresults to improve the worst-case bounds for coloring k -colorable graphs for constant k > 3 as well.