Faster Edge Coloring by Partition Sieving

Abstract

In the Edge Coloring problem, we are given an undirected graph G with n vertices and m edges, and are tasked with finding the smallest positive integer k so that the edges of G can be assigned k colors in such a way that no two edges incident to the same vertex are assigned the same color. Edge Coloring is a classic NP-hard problem, and so significant research has gone into designing fast exponential-time algorithms for solving Edge Coloring and its variants exactly. Prior work showed that Edge Coloring can be solved in 2m poly(n) time and polynomial space, and in graphs with average degree d in 2(1−εd)m poly(n) time and exponential space, where εd = (1/d)Θ(d3). We present an algorithm that solves Edge Coloring in 2m−3n/5 poly(n) time and polynomial space. Our result is the first algorithm for this problem which simultaneously runs in faster than 2m poly(m) time and uses only polynomial space. In graphs of average degree d, our algorithm runs in 2(1−6/(5d))m poly(n) time, which has far better dependence in d than previous results. We also consider a generalization of Edge Coloring called List Edge Coloring, where each edge e in the input graph comes with a list Le ⊆ {1,..., k} of colors, and we must determine whether we can assign each edge a color from its list so that no two edges incident to the same vertex receive the same color. We show that this problem can be solved in 2(1−6/(5k))m poly(n) time and polynomial space. The previous best algorithm for List Edge Coloring took 2m poly(n) time and space. Our algorithms are algebraic, and work by constructing a special polynomial P based off the input graph that contains a multilinear monomial (i.e., a monomial where every variable has degree at most one) if and only if the answer to the List Edge Coloring problem on the input graph is YES. We then solve the problem by detecting multilinear monomials in P. Previous work also employed such monomial detection techniques to solve Edge Coloring. We obtain faster algorithms both by carefully constructing our polynomial P, and by improving the runtimes for certain structured monomial detection problems using a technique we call partition sieving.