2026/07/29 by Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
Computer Science · Mathematics · #cs.CC #cs.DS #math.CO
40 pages, 5 figures. FOCS 2026
arxiv created 2026/07/29 · arxiv updated 2026/07/30
Graph k-coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a k-coloring over the set of all k-colorable graphs on n vertices. A highly influential result of Dyer-Frieze from 1989 gave an algorithm with O(n2) average runtime for constant k. This quadratic runtime appeared natural (and possibly even optimal) since almost all k-colorable graphs have Θ(n2) edges, so one needs at least this time in order to read the (entire) input. However, this was later improved by Kučera in 1995 to average runtime O(n2/k) for every k ≤ nc where c ∈ (0, 1). Nevertheless, in the most interesting case of k = O(1), the best-known bound remained quadratic in n. The true average complexity of the k-coloring problem has remained elusive for the last three decades. We break the longstanding quadratic barrier. Our main result in this paper shows that the exact average-case complexity of this fundamental problem is Θ(nk) for every k ≤ nc' and some c' ∈ (0, 1). For k = O(1), this reveals the average sublinear nature of k-colorability: the average-case complexity is linear in n, and thus sublinear in the size of the input. We further show that our Θ(nk) average runtime is optimal, since a simple bound proves that every algorithm that correctly k-colors all k-colorable graphs requires Ω(n k) average runtime. Our proofs draw on ideas from sublinear and local algorithms and also yield a local computation algorithm (LCA) for k-coloring with average-case probe complexity poly(k). A key new ingredient in our algorithm is a method for certifying the unique colorability of random subgraphs, using tools from the theory of graph regularity.