2026-08-15T12:21:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9090 2024-03-06T10:43:20Z ddc:004 open_access

Finer Tight Bounds for Coloring on Clique-Width Lampis, Michael Clique-width SETH Coloring 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 the complexity of k-Coloring parameterized by clique-width for any fixed k, under the SETH. Specifically, we show that for all k >= 3,epsilon>0, k-Coloring cannot be solved in time O^*((2^k-2-epsilon)^{cw}), and give an algorithm running in time O^*((2^k-2)^{cw}). Thus, if the SETH is true, 2^k-2 is the "correct" base of the exponent for every 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^*({k choose floor[k/2]}^{mtw}). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Lampis 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.86 urn:nbn:de:0030-drops-90903 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.86 eng https://creativecommons.org/licenses/by/3.0/legalcode