Tight Lower Bounds for List Edge Coloring
share
The fastest algorithms for edge coloring run in time 2^m n^O(1), where m and n are the number of edges and vertices of the input graph, respectively. For dense graphs, this bound becomes 2^Θ(n^2). This is a somewhat unique situation, since most of the studied graph problems admit algorithms running in time 2^O(n n). It is a notorious open problem to either show an algorithm for edge coloring running in time 2^o(n^2) or to refute it, assuming Exponential Time Hypothesis (ETH) or other well established assumption. We notice that the same question can be asked for list edge coloring, a well-studied generalization of edge coloring where every edge comes with a set (often called a list) of allowed colors. Our main result states that list edge coloring for simple graphs does not admit an algorithm running in time 2^o(n^2), unless ETH fails. Interestingly, the algorithm for edge coloring running in time 2^m n^O(1) generalizes to the list version without any asymptotic slow-down. Thus, our lower bound is essentially tight. This also means that in order to design an algorithm running in time 2^o(n^2) for edge coloring, one has to exploit its special features compared to the list version.
READ FULL TEXT