Document Open Access Logo

Tight Lower Bounds for the Complexity of Multicoloring

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.18.pdf
  • Filesize: 0.61 MB
  • 14 pages

Document Identifiers

Author Details

Marthe Bonamy
Lukasz Kowalik
Michal Pilipczuk
Arkadiusz Socala
Marcin Wrochna

Cite As Get BibTex

Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna. Tight Lower Bounds for the Complexity of Multicoloring. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.18

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.

Subject Classification

Keywords
  • multicoloring
  • Kneser graph homomorphism
  • ETH lower bound

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Hasan Abasi, Nader H. Bshouty, Ariel Gabizon, and Elad Haramaty. On r-simple k-path. In MFCS 2015, volume 8635 of Lecture Notes in Computer Science, pages 1-12. Springer, 2014. Google Scholar
  2. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Comput., 39(2):546-563, 2009. Google Scholar
  3. Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna. Tight lower bounds for the complexity of multicoloring. CoRR, abs/1607.03432, 2016. URL: http://arxiv.org/abs/1607.03432.
  4. Nader H. Bshouty. Optimal algorithms for the coin weighing problem with a spring scale. In COLT 2009, 2009. Google Scholar
  5. Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen. Online multi-coloring with advice. In WAOA 2014, volume 8952 of Lecture Notes in Computer Science, pages 83-94. Springer, 2014. Google Scholar
  6. V. Chvátal, M. R. Garey, and D. S. Johnson. Two results concerning multicoloring. In Algorithmic Aspects of Combinatorics, volume 2 of Annals of Discrete Math., pages 151-154. Elsevier, 1978. Google Scholar
  7. Vasek Chvátal. Mastermind. Combinatorica, 3(3):325-329, 1983. URL: http://dx.doi.org/10.1007/BF02579188.
  8. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 2009. Google Scholar
  9. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socała. Tight bounds for Graph Homomorphism and Subgraph Isomorphism. In SODA 2016, pages 1643-1649, 2016. Google Scholar
  10. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  11. Reinhard Diestel. Graph Theory. Springer-Verlag Heidelberg, 2010. Google Scholar
  12. David C. Fisher. Fractional colorings with large denominators. J. Graph Theory, 20(4):403-409, 1995. Google Scholar
  13. Fedor V. Fomin, Pinar Heggernes, and Dieter Kratsch. Exact algorithms for graph homomorphisms. Theory Comput. Syst., 41(2):381-393, 2007. URL: http://dx.doi.org/10.1007/s00224-007-2007-x.
  14. Ariel Gabizon, Daniel Lokshtanov, and Michal Pilipczuk. Fast algorithms for parameterized problems with relaxed disjointness constraints. In ESA 2015, volume 9294 of Lecture Notes in Computer Science, pages 545-556. Springer, 2015. Google Scholar
  15. Vladimir Grebinski and Gregory Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica, 28(1):104-124, 2000. URL: https://hal.inria.fr/inria-00073517, URL: http://dx.doi.org/10.1007/s004530010033.
  16. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. Corrigendum available at: http://dx.doi.org/10.1007/BF02579139. URL: http://dx.doi.org/10.1007/BF02579273.
  17. Magnús M. Halldórsson and Guy Kortsarz. Multicoloring: Problems and techniques. In MFCS 2013, volume 3153 of Lecture Notes in Computer Science, pages 25-41. Springer, 2004. Google Scholar
  18. Magnús M. Halldórsson, Guy Kortsarz, Andrzej Proskurowski, Ravit Salman, Hadas Shachnai, and Jan Arne Telle. Multicoloring trees. Inf. Comput., 180(2):113-129, 2003. Google Scholar
  19. Frédéric Havet. Channel assignment and multicolouring of the induced subgraphs of the triangular lattice. Discrete Math., 233(1-3):219-231, 2001. Google Scholar
  20. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. J. Comb. Theory, Ser. B, 48(1):92-110, 1990. URL: http://dx.doi.org/10.1016/0095-8956(90)90132-J.
  21. Qiang-Sheng Hua, Yuexuan Wang, Dongxiao Yu, and Francis C. M. Lau. Dynamic programming based algorithms for set multicover and multiset multicover problems. Theor. Comput. Sci., 411(26-28):2467-2474, 2010. Google Scholar
  22. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  24. Mustapha Kchikech and Olivier Togni. Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes. Discrete Math. Theor. Comput. Sci., 8(1):159-172, 2006. Google Scholar
  25. Fabian Kuhn. Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in constant time. In STACS 2009, volume 3 of LIPIcs, pages 613-624. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany, 2009. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2009.1852.
  26. Wensong Lin. Multicoloring and Mycielski construction. Discrete Math., 308(16):3565-3573, 2008. Google Scholar
  27. Bernt Lindström. On a combinatorial problem in number theory. Canad. Math. Bull, 8(4):477-490, 1965. URL: http://dx.doi.org/10.4153/CMB-1965-034-2.
  28. László Lovász. Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A, 25(3):319-324, 1978. Google Scholar
  29. Dániel Marx. The complexity of tree multicolorings. In MFSC 2002, volume 2420 of Lecture Notes in Computer Science, pages 532-542. Springer, 2002. Google Scholar
  30. Colin McDiarmid and Bruce A. Reed. Channel assignment and weighted coloring. Networks, 36(2):114-117, 2000. Google Scholar
  31. J. W. Moon and L. Moser. On cliques in graphs. Israel J. Math., 3(1):23-28, 1965. Google Scholar
  32. Jesper Nederlof. Inclusion exclusion for hard problems. Master’s thesis, Department of Information and Computer Science, Utrecht University, 2008. Available at URL: http://www.win.tue.nl/~jnederlo/MScThesis.pdf.
  33. K. S. Sudeep and Sundar Vishwanathan. A technique for multicoloring triangle-free hexagonal graphs. Discrete Math., 300(1-3):256-259, 2005. Google Scholar
  34. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Appl. Math., 8(1):85-89, 1984. URL: http://dx.doi.org/10.1016/0166-218X(84)90081-7.
  35. Magnus Wahlström. New plain-exponential time classes for graph homomorphism. Theory Comput. Syst., 49(2):273-282, 2011. URL: http://dx.doi.org/10.1007/s00224-010-9261-z.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact