{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T00:41:51Z","timestamp":1771980111484,"version":"3.50.1"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T00:00:00Z","timestamp":1542326400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001742","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["11\/6711"],"award-info":[{"award-number":["11\/6711"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Norges Forskningsr\u00e5d","doi-asserted-by":"publisher","award":["249994 and 263317"],"award-info":[{"award-number":["249994 and 263317"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"\n M\n AX<\/jats:sc>\n -C\n UT<\/jats:sc>\n , E\n DGE<\/jats:sc>\n D\n OMINATING<\/jats:sc>\n S\n ET<\/jats:sc>\n , G\n RAPH<\/jats:sc>\n C\n OLORING<\/jats:sc>\n , and H\n AMILTONIAN<\/jats:sc>\n C\n YCLE<\/jats:sc>\n on graphs of bounded clique-width have received significant attention as they can be formulated in MSO\n 2<\/jats:sub>\n (and, therefore, have linear-time algorithms on bounded treewidth graphs by the celebrated Courcelle\u2019s theorem), but cannot be formulated in MSO\n 1<\/jats:sub>\n (which would have yielded linear-time algorithms on bounded clique-width graphs by a well-known theorem of Courcelle, Makowsky, and Rotics). Each of these problems can be solved in time\n g<\/jats:italic>\n (\n k<\/jats:italic>\n )\n n<\/jats:italic>\n \n f<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n on graphs of clique-width\n k<\/jats:italic>\n . Fomin et al. (2010) showed that the running times cannot be improved to\n g<\/jats:italic>\n (\n k<\/jats:italic>\n )\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n assuming W[1]\u2260FPT. However, this does not rule out non-trivial improvements to the exponent\n f<\/jats:italic>\n (\n k<\/jats:italic>\n ) in the running times. In a follow-up paper, Fomin et al. (2014) improved the running times for E\n DGE<\/jats:sc>\n D\n OMINATING<\/jats:sc>\n S\n ET<\/jats:sc>\n and M\n AX<\/jats:sc>\n -C\n UT<\/jats:sc>\n to\n n<\/jats:italic>\n \n O<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n , and proved that these problems cannot be solved in time\n g<\/jats:italic>\n (\n k<\/jats:italic>\n )\n n<\/jats:italic>\n \n o<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n unless ETH fails. Thus, prior to this work, E\n DGE<\/jats:sc>\n D\n OMINATING<\/jats:sc>\n S\n ET<\/jats:sc>\n and M\n AX<\/jats:sc>\n -C\n UT<\/jats:sc>\n were known to have tight\n n<\/jats:italic>\n \n \u0398 (\n k<\/jats:italic>\n )\n <\/jats:sup>\n algorithmic upper and lower bounds.\n <\/jats:p>\n \n In this article, we provide lower bounds for H\n AMILTONIAN<\/jats:sc>\n C\n YCLE<\/jats:sc>\n and G\n RAPH<\/jats:sc>\n C\n OLORING<\/jats:sc>\n . For H\n AMILTONIAN<\/jats:sc>\n C\n YCLE<\/jats:sc>\n , our lower bound\n g<\/jats:italic>\n (\n k<\/jats:italic>\n )\n n<\/jats:italic>\n \n o<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n matches asymptotically the recent upper bound\n n<\/jats:italic>\n \n O<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n due to Bergougnoux, Kant\u00e9, and Kwon (2017).\n <\/jats:p>\n \n As opposed to the asymptotically tight\n n<\/jats:italic>\n \n \u0398(\n k<\/jats:italic>\n )\n <\/jats:sup>\n bounds for E\n DGE<\/jats:sc>\n D\n OMINATING<\/jats:sc>\n S\n ET<\/jats:sc>\n , M\n AX<\/jats:sc>\n -C\n UT<\/jats:sc>\n , and H\n AMILTONIAN<\/jats:sc>\n C\n YCLE<\/jats:sc>\n , the G\n RAPH<\/jats:sc>\n C\n OLORING<\/jats:sc>\n problem has an upper bound of\n n<\/jats:italic>\n \n O<\/jats:italic>\n (2\n \n k<\/jats:italic>\n <\/jats:sup>\n )\n <\/jats:sup>\n and a lower bound of merely\n n<\/jats:italic>\n \n o<\/jats:italic>\n (\u221a [4]\n k<\/jats:italic>\n )\n <\/jats:sup>\n (implicit from the W[1]-hardness proof). In this article, we close the gap for G\n RAPH<\/jats:sc>\n C\n OLORING<\/jats:sc>\n by proving a lower bound of\n n<\/jats:italic>\n \n 2\n \n o<\/jats:italic>\n (\n k<\/jats:italic>\n )\n <\/jats:sup>\n <\/jats:sup>\n . This shows that G\n RAPH<\/jats:sc>\n C\n OLORING<\/jats:sc>\n behaves qualitatively different from the other three problems. To the best of our knowledge, G\n RAPH<\/jats:sc>\n C\n OLORING<\/jats:sc>\n is the first natural problem known to require exponential dependence on the parameter in the exponent of\n n<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/3280824","type":"journal-article","created":{"date-parts":[[2018,11,16]],"date-time":"2018-11-16T13:08:54Z","timestamp":1542373734000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Clique-width III"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"Department of Informatics, University of Bergen, Norway and The Institute of Mathematical Sciences, HBNI, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Computer Science Department, Ben-Gurion University of the Negev, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-62127-2_11"},{"key":"e_1_2_1_3_1","volume-title":"Nonserial Dynamic Programming","author":"Bertel\u00e9 Umberto","unstructured":"Umberto Bertel\u00e9 and Francesco Brioschi . 1972. Nonserial Dynamic Programming . Academic Press . Umberto Bertel\u00e9 and Francesco Brioschi. 1972. Nonserial Dynamic Programming. Academic Press."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01758777"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.03.008"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.05.022"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_6"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.03.020"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701385351"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/1992260302571"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002249910009"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00184-5"},{"key":"e_1_2_1_16_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/130947076"},{"key":"e_1_2_1_18_1","volume-title":"Graph Theory","author":"Diestel Reinhard","unstructured":"Reinhard Diestel . 2010. Graph Theory ( 4 th ed.). Springer-Verlag , Heidelberg, Germany . Reinhard Diestel. 2010. Graph Theory (4th ed.). Springer-Verlag, Heidelberg, Germany.","edition":"4"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1789694.1789703"},{"key":"e_1_2_1_20_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"2013","unstructured":"Rodney G. Downey and Michael R . Fellows . 2013 . Fundamentals of Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 2013. Fundamentals of Parameterized Complexity. Springer."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/647682.732478"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/070687256"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958026"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/130910932"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2004.01.007"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00725-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645208"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science)","volume":"5344","author":"Godlin Benny","unstructured":"Benny Godlin , Tomer Kotek , and Johann A. Makowsky . 2008. Evaluations of graph polynomials . In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science) , Vol. 5344 . 183--194. Benny Godlin, Tomer Kotek, and Johann A. Makowsky. 2008. Evaluations of graph polynomials. In Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (Lecture Notes in Computer Science), Vol. 5344. 183--194."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2006.03.048"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685920"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm052"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 468--476","author":"Kobler Daniel","year":"2001","unstructured":"Daniel Kobler and Udi Rotics . 2001 . Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract) . In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 468--476 . Daniel Kobler and Udi Rotics. 2001. Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract). In Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. 468--476."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00198-1"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-10(1:18)2014"},{"key":"e_1_2_1_38_1","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov , D\u00e1niel Marx , and Saket Saurabh . 2011 . Lower bounds based on the exponential time hypothesis . Bull. EATCS 105 (2011), 41 -- 72 . DOI:cs\/article\/view\/96 Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41--72. DOI:cs\/article\/view\/96","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11917496_18"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming","volume":"55","author":"Marx D\u00e1niel","year":"2016","unstructured":"D\u00e1niel Marx and Valia Mitsou . 2016 . Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth . In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming , Vol. 55 . 28:1--28:15. D\u00e1niel Marx and Valia Mitsou. 2016. Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, Vol. 55. 28:1--28:15."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.10.006"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1435375.1435385"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.03.043"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.03.014"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90026-4"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3280824","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3280824","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:01:51Z","timestamp":1750208511000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3280824"}},"subtitle":["Hamiltonian Cycle and the Odd Case of Graph Coloring"],"short-title":[],"issued":{"date-parts":[[2018,11,16]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3280824"],"URL":"https:\/\/doi.org\/10.1145\/3280824","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,16]]},"assertion":[{"value":"2018-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}