License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2017.18
URN: urn:nbn:de:0030-drops-78527
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7852/
Go to the corresponding LIPIcs Volume Portal

Bonamy, Marthe ; Kowalik, Lukasz ; Pilipczuk, Michal ; Socala, Arkadiusz ; Wrochna, Marcin

Tight Lower Bounds for the Complexity of Multicoloring

pdf-format:
LIPIcs-ESA-2017-18.pdf (0.6 MB)

Abstract

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.

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:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Kirk Pruhs and Christian Sohler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7852},
  URN =		{urn:nbn:de:0030-drops-78527},
  doi =		{10.4230/LIPIcs.ESA.2017.18},
  annote =	{Keywords: multicoloring, Kneser graph homomorphism, ETH lower bound}
}

Keywords: multicoloring, Kneser graph homomorphism, ETH lower bound
Collection: 25th Annual European Symposium on Algorithms (ESA 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI