2026-08-10T17:54:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7852 2024-03-06T10:41:17Z ddc:004 open_access

Tight Lower Bounds for the Complexity of Multicoloring Bonamy, Marthe Kowalik, Lukasz Pilipczuk, Michal Socala, Arkadiusz Wrochna, Marcin multicoloring Kneser graph homomorphism ETH lower bound In the multicoloring problem, also known as (a:b)-coloring or b-fold coloring, we are given a graph G and a set of a colors, and the task is to assign a subset of b colors to each vertex of G so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the b=1 case) is equivalent to finding a homomorphism to the Kneser graph KG_{a,b}, and gives relaxations approaching the fractional chromatic number. We study the complexity of determining whether a graph has an (a:b)-coloring. Our main result is that this problem does not admit an algorithm with running time f(b) * 2^{o(log b) n}, for any computable f(b), unless the Exponential Time Hypothesis (ETH) fails. A (b+1)^n * poly(n)-time algorithm due to Nederlof [2008] shows that this is tight. A direct corollary of our result is that the graph homomorphism problem does not admit a 2^O(n+h) algorithm unless ETH fails, even if the target graph is required to be a Kneser graph. This refines the understanding given by the recent lower bound of Cygan et al. [SODA 2016]. The crucial ingredient in our hardness reduction is the usage of detecting matrices of Lindström [Canad. Math. Bull., 1965], which is a combinatorial tool that, to the best of our knowledge, has not yet been used for proving complexity lower bounds. As a side result, we prove that the running time of the algorithms of Abasi et al. [MFCS 2014] and of Gabizon et al. [ESA 2015] for the r-monomial detection problem are optimal under ETH. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marthe Bonamy and Lukasz Kowalik and Michal Pilipczuk and Arkadiusz Socala and Marcin Wrochna 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.18 urn:nbn:de:0030-drops-78527 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.18 eng https://creativecommons.org/licenses/by/3.0/legalcode