Finer Tight Bounds for Coloring on Clique-Width
Michael Lampis · SIAM Journal on Discrete Mathematics · 2020
We revisit the complexity of the classical $k$-Coloring problem parameterized by clique-width. This is a very well-studied problem that becomes highly intractable when the number of colors $k$ is large. However, much less is known on its complexity for small, concrete values of $k$. In this paper, we completely determine, under the Strong Exponential Time Hypothesis (SETH), for any fixed constant $k$, the complexity of $k$-Coloring parameterized by clique-width. Specifically, we show that for all $k\ge 3,\epsilon>0$, $k$-Coloring cannot be solved in time $O^*\left((2^k-2-\epsilon)^{{cw}}\right)$, and give an algorithm running in time $O^*\left((2^k-2)^{{cw}}\right)$. Thus, if the SETH is true, $2^k-2$ is the “correct” base of the exponent for every fixed $k$. Along the way, we also consider the complexity of $k$-Coloring parameterized by the related parameter modular treewidth (${mtw}$). In this case we show that the “correct” running time under the SETH is $O^*\big({k\choose \lfloor k/2\rfloor}^{{mtw}}\big)$. If we base our results on a weaker assumption (the ETH), they imply that $k$-Coloring cannot be solved in time $n^{o({cw})}$, even on instances with $O(\log n)$ colors.