Bonamy, Marthe ;
Kowalik, Lukasz ;
Pilipczuk, Michal ;
Socala, Arkadiusz ;
Wrochna, Marcin
Tight Lower Bounds for the Complexity of Multicoloring
Abstract
In the multicoloring problem, also known as (a:b)coloring or bfold 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 rmonomial detection problem are optimal under ETH.
BibTeX  Entry
@InProceedings{bonamy_et_al:LIPIcs:2017:7852,
author = {Marthe Bonamy and Lukasz Kowalik and Michal Pilipczuk and Arkadiusz Socala and Marcin Wrochna},
title = {{Tight Lower Bounds for the Complexity of Multicoloring}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {18:118:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770491},
ISSN = {18688969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7852},
URN = {urn:nbn:de:0030drops78527},
doi = {10.4230/LIPIcs.ESA.2017.18},
annote = {Keywords: multicoloring, Kneser graph homomorphism, ETH lower bound}
}
2017
Keywords: 

multicoloring, Kneser graph homomorphism, ETH lower bound 
Seminar: 

25th Annual European Symposium on Algorithms (ESA 2017)

Issue date: 

2017 
Date of publication: 

2017 