{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:27:47Z","timestamp":1750220867149,"version":"3.41.0"},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,4,2]],"date-time":"2019-04-02T00:00:00Z","timestamp":1554163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["677651"],"award-info":[{"award-number":["677651"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/11\/D\/ST6\/03073, 2015\/17\/N\/ST6\/01224"],"award-info":[{"award-number":["2013\/11\/D\/ST6\/03073, 2015\/17\/N\/ST6\/01224"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,9,30]]},"abstract":"<jats:p>\n            In the\n            <jats:italic>multicoloring<\/jats:italic>\n            problem, also known as (\n            <jats:italic>a<\/jats:italic>\n            :\n            <jats:italic>b<\/jats:italic>\n            )-\n            <jats:italic>coloring<\/jats:italic>\n            or\n            <jats:italic>b-fold coloring<\/jats:italic>\n            , we are given a graph\n            <jats:italic>G<\/jats:italic>\n            and a set of\n            <jats:italic>a<\/jats:italic>\n            colors, and the task is to assign a subset of\n            <jats:italic>b<\/jats:italic>\n            colors to each vertex of\n            <jats:italic>G<\/jats:italic>\n            so that adjacent vertices receive disjoint color subsets. This natural generalization of the classic coloring problem (the\n            <jats:italic>b<\/jats:italic>\n            =1 case) is equivalent to finding a homomorphism to the Kneser graph\n            <jats:italic>KG<\/jats:italic>\n            <jats:sub>\n              <jats:italic>a,b<\/jats:italic>\n            <\/jats:sub>\n            and gives relaxations approaching the fractional chromatic number.\n          <\/jats:p>\n          <jats:p>\n            We study the complexity of determining whether a graph has an (\n            <jats:italic>a<\/jats:italic>\n            :\n            <jats:italic>b<\/jats:italic>\n            )-coloring. Our main result is that this problem does not admit an algorithm with runtime\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>b<\/jats:italic>\n            )\u010b 2\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (log\n              <jats:italic>b<\/jats:italic>\n              )\u010b\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            for any computable\n            <jats:italic>f(b)<\/jats:italic>\n            unless the Exponential Time Hypothesis (ETH) fails. A (\n            <jats:italic>b<\/jats:italic>\n            +1)\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u010b poly(\n            <jats:italic>n<\/jats:italic>\n            )-time algorithm due to Nederlof [33] shows that this is tight. A direct corollary of our result is that the graph homomorphism problem does not admit a 2\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              +\n              <jats:italic>h<\/jats:italic>\n              )\n            <\/jats:sup>\n            algorithm unless the 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. [9].\n          <\/jats:p>\n          <jats:p>\n            The crucial ingredient in our hardness reduction is the usage of\n            <jats:italic>detecting matrices<\/jats:italic>\n            of Lindstr\u00f6m\u00a0[28], 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 runtime of the algorithms of Abasi et al. [1] and of Gabizon et al. [14] for the\n            <jats:italic>r<\/jats:italic>\n            -monomial detection problem are optimal under\u00a0the ETH.\n          <\/jats:p>","DOI":"10.1145\/3313906","type":"journal-article","created":{"date-parts":[[2019,4,4]],"date-time":"2019-04-04T18:38:37Z","timestamp":1554403117000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Tight Lower Bounds for the Complexity of Multicoloring"],"prefix":"10.1145","volume":"11","author":[{"given":"Marthe","family":"Bonamy","sequence":"first","affiliation":[{"name":"CNRS, LaBRI, Bordeaux, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0142Ukasz","family":"Kowalik","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Pilipczuk","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arkadiusz","family":"Soca\u0142a","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marcin","family":"Wrochna","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,4,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44465-8_1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 22nd Conference on Learning Theory. McGill University, 1--10","author":"Bshouty Nader H.","year":"2009","unstructured":"Nader H. Bshouty . 2009 . Optimal algorithms for the coin weighing problem with a spring scale . In Proceedings of the 22nd Conference on Learning Theory. McGill University, 1--10 . https:\/\/www.cs.mcgill.ca\/&sim;colt2009\/proceedings.html. Nader H. Bshouty. 2009. Optimal algorithms for the coin weighing problem with a spring scale. In Proceedings of the 22nd Conference on Learning Theory. McGill University, 1--10. https:\/\/www.cs.mcgill.ca\/&sim;colt2009\/proceedings.html."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1156"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 14th International Workshop on Approximation and Online Algorithms (WAOA\u201916)","volume":"8952","author":"Christ Marie G.","unstructured":"Marie G. Christ , Lene M. Favrholdt , and Kim S. Larsen . 2016. Online multi-coloring with advice . In Proceedings of the 14th International Workshop on Approximation and Online Algorithms (WAOA\u201916) , Klaus Jansen and Monaldo Mastrolilli (Eds.) , Vol. 8952 . Springer, Berlin, 83--94. Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen. 2016. Online multi-coloring with advice. In Proceedings of the 14th International Workshop on Approximation and Online Algorithms (WAOA\u201916), Klaus Jansen and Monaldo Mastrolilli (Eds.), Vol. 8952. Springer, Berlin, 83--94."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579188"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916)","volume":"2","author":"Chv\u00e1tal V.","unstructured":"V. Chv\u00e1tal , M. R. Garey , and D. S. Johnson . 1978. Two results concerning multicoloring . In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916) , Robert Krauthgamer (Ed.) , Vol. 2 . Elsevier, 151--154. V. Chv\u00e1tal, M. R. Garey, and D. S. Johnson. 1978. Two results concerning multicoloring. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201916), Robert Krauthgamer (Ed.), Vol. 2. Elsevier, 151--154."},{"key":"e_1_2_1_8_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms. The MIT Press Cambridge MA.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms. The MIT Press Cambridge MA."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051094"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_10_1","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141ukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"volume-title":"Graph Theory","author":"Diestel Reinhard","key":"e_1_2_1_11_1","unstructured":"Reinhard Diestel . 2010. Graph Theory . Springer-Verlag Heidelberg . Reinhard Diestel. 2010. Graph Theory. Springer-Verlag Heidelberg."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190200403"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-2007-x"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_46"},{"key":"e_1_2_1_15_1","volume-title":"Royle","author":"Godsil Chris","year":"2001","unstructured":"Chris Godsil and Gordon F . Royle . 2001 . Algebraic Graph Theory. Springer . Chris Godsil and Gordon F. Royle. 2001. Algebraic Graph Theory. Springer."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010033"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_2_1_18_1","volume-title":"Halld\u00f3rsson and Guy Kortsarz","author":"Magn\u00fas","year":"2004","unstructured":"Magn\u00fas M. Halld\u00f3rsson and Guy Kortsarz . 2004 . Multicoloring : Problems and techniques. In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201913), Krishnendu Chatterjee and Jir\u00ed Sgall (Eds.), Vol. 3153 . Springer , Berlin, 25--41. Magn\u00fas M. Halld\u00f3rsson and Guy Kortsarz. 2004. Multicoloring: Problems and techniques. In Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS\u201913), Krishnendu Chatterjee and Jir\u00ed Sgall (Eds.), Vol. 3153. Springer, Berlin, 25--41."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(02)00032-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00241-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.02.016"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_25_1","first-page":"159","article-title":"Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes","volume":"8","author":"Kchikech Mustapha","year":"2006","unstructured":"Mustapha Kchikech and Olivier Togni . 2006 . Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes . Discrete Math. Theor. Comput. Sci. 8 , 1 (2006), 159 -- 172 . Mustapha Kchikech and Olivier Togni. 2006. Approximation algorithms for multicoloring planar graphs and powers of square and triangular meshes. Discrete Math. Theor. Comput. Sci. 8, 1 (2006), 159--172.","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909)","volume":"3","author":"Kuhn Fabian","year":"2009","unstructured":"Fabian Kuhn . 2009 . Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in constant time . In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909) , Susanne Albers and Jean-Yves Marion (Eds.) , Vol. 3 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Germany, 613--624. Fabian Kuhn. 2009. Local multicoloring algorithms: Computing a nearly-optimal TDMA schedule in constant time. In Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science (STACS\u201909), Susanne Albers and Jean-Yves Marion (Eds.), Vol. 3. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Germany, 613--624."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.07.015"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4153\/CMB-1965-034-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90022-5"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/645731.668215"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/1097-0037(200009)36:2<114::AID-NET6>3.0.CO;2-G"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760024"},{"key":"e_1_2_1_33_1","volume-title":"Inclusion exclusion for hard problems. Master\u2019s thesis. Department of Information and Computer Science","author":"Nederlof Jesper","year":"2019","unstructured":"Jesper Nederlof . 2008. Inclusion exclusion for hard problems. Master\u2019s thesis. Department of Information and Computer Science , Utrecht University . Retrieved February 26, 2019 from http:\/\/www.win.tue.nl\/jnederlo\/MScThesis.pdf. Jesper Nederlof. 2008. Inclusion exclusion for hard problems. Master\u2019s thesis. Department of Information and Computer Science, Utrecht University. Retrieved February 26, 2019 from http:\/\/www.win.tue.nl\/jnederlo\/MScThesis.pdf."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.06.002"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90081-7"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9261-z"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313906","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313906","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:23:46Z","timestamp":1750202626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,2]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,9,30]]}},"alternative-id":["10.1145\/3313906"],"URL":"https:\/\/doi.org\/10.1145\/3313906","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,4,2]]},"assertion":[{"value":"2017-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-04-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}