If Edge Coloring is Hard under SETH, then SETH is False

Abstract

The Edge Coloring problem is notoriously hard: it is still unknown whether it can be solved in time $2^{o(n^2)}$ (let alone $2^{O(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^{\hat{I}\text{c◯}(n^2)}$ 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 $\hat{I}{\pm }^{n^2}$ (where $\hat{I}\pm >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.

SOSA 2024