
Finer Tight Bounds for Coloring on Clique-Width
Lampis, Michael (2019), Finer Tight Bounds for Coloring on Clique-Width, SIAM Journal on Discrete Mathematics, 34, 3, p. 1538–1558. 10.1137/19M1280326
View/ Open
Type
Article accepté pour publication ou publiéDate
2019Journal name
SIAM Journal on Discrete MathematicsVolume
34Number
3Publisher
SIAM - Society for Industrial and Applied Mathematics
Pages
1538–1558
Publication identifier
Metadata
Show full item recordAuthor(s)
Lampis, MichaelLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.Subjects / Keywords
Clique-width; SETH; ColoringRelated items
Showing items related by title and author.
-
Lampis, Michael (2018) Communication / Conférence
-
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2019) Article accepté pour publication ou publié
-
Katsikarelis, Ioannis; Lampis, Michael; Paschos, Vangelis (2017) Communication / Conférence
-
Dublois, Louis; Lampis, Michael; Paschos, Vangelis (2021) Communication / Conférence
-
Lampis, Michael; Mitsou, Valia (2021) Communication / Conférence