If Edge Coloring is Hard under SETH, then SETH is False
Alexander S. Kulikov, Ivan Mihajlin · Society for Industrial and Applied Mathematics eBooks · 2024
The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time 2o(n2)(let alone 2O(n) where n is the number of nodes of the input graph. Can one explain the lack of such upper bounds by deriving a lower bound 2Ω(n2) from a lower bound for SAT, 3-SUM, or APSP? In this note, we provide a negative answer for this question: if there is a reduction showing that Edge Coloring cannot be solved faster than in αn2 (where α > 1 is an explicit constant) under a hypothesis that known algorithms for one of the problems mentioned above are optimal, then the corresponding hypothesis is false.