{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:10:10Z","timestamp":1750162210539,"version":"3.41.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T00:00:00Z","timestamp":1748563200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T00:00:00Z","timestamp":1748563200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["grant agreement No. 853234","grant agreement No. 853234"],"award-info":[{"award-number":["grant agreement No. 853234","grant agreement No. 853234"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In the C<jats:sc>hoosability<\/jats:sc> problem (or list chromatic number problem), for a given graph <jats:italic>G<\/jats:italic>, we need to find the smallest <jats:italic>k<\/jats:italic> such that <jats:italic>G<\/jats:italic> admits a list coloring for any list assignment where all lists contain at least <jats:italic>k<\/jats:italic> colors. The problem is tightly connected with the well-studied C<jats:sc>oloring<\/jats:sc> and L<jats:sc>ist <\/jats:sc> C<jats:sc>oloring<\/jats:sc> problems. However, the knowledge of the complexity landscape for the C<jats:sc>hoosability<\/jats:sc> problem is pretty scarce. Moreover, most of the known results only provide lower bounds for its computational complexity and do not provide ways to cope with the intractability. The main objective of our paper is to construct the first non-trivial exact exponential algorithms for the C<jats:sc>hoosability<\/jats:sc> problem, and complete the picture with parameterized results. Specifically, we present the first single-exponential algorithm for the decision version of the problem with fixed <jats:italic>k<\/jats:italic>. This result answers an implicit question from Eppstein on a stackexchange thread discussing upper bounds on the union of lists assigned to vertices. We also present a <jats:inline-formula>\n              <jats:tex-math>$$2^{n^2} poly(n)$$<\/jats:tex-math>\n            <\/jats:inline-formula> time algorithm for the general C<jats:sc>hoosability<\/jats:sc> problem. In the parameterized setting, we give a polynomial kernel for the problem parameterized by vertex cover, and algorithms that run in FPT time when parameterized by a size of a clique-modulator and by the dual parameterization <jats:inline-formula>\n              <jats:tex-math>$$n-k$$<\/jats:tex-math>\n            <\/jats:inline-formula>. Additionally, we show that C<jats:sc>hoosability<\/jats:sc> admits a significant running time improvement if it is parameterized by cutwidth in comparison with the parameterization by treewidth studied by Marx and Mitsou\u00a0[ICALP\u201916]. On the negative side, we provide a lower bound parameterized by a size of a modulator to split graphs under assumption of the Exponential Time Hypothesis.<\/jats:p>","DOI":"10.1007\/s00236-025-00492-0","type":"journal-article","created":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T10:12:51Z","timestamp":1748599971000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Exact and parameterized algorithms for choosability"],"prefix":"10.1007","volume":"62","author":[{"given":"Ivan","family":"Bliznets","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,30]]},"reference":[{"key":"492_CR1","first-page":"1","volume":"187","author":"N Alon","year":"1993","unstructured":"Alon, N.: Restricted colorings of graphs. Surveys in combinatorics 187, 1\u201333 (1993)","journal-title":"Surveys in combinatorics"},{"key":"492_CR2","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/BF01204715","volume":"12","author":"N Alon","year":"1992","unstructured":"Alon, N., Tarsi, M.: Colorings and orientations of graphs. Combinatorica 12, 125\u2013134 (1992)","journal-title":"Combinatorica"},{"key":"492_CR3","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Johnson, D.S., Feige, U. (eds.) Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, ACM, pp. 67\u201374 (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"492_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets m\u00f6bius: fast subset convolution. In: Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, pp. 67\u201374 (2007)","DOI":"10.1145\/1250790.1250801"},{"key":"492_CR5","doi-asserted-by":"crossref","unstructured":"Bliznets, I., Hecher, M.: Tight double exponential lower bounds. To appear in Theory and Applications of Models of Computation (TAMC) (2024)","DOI":"10.1007\/978-981-97-2340-9_11"},{"issue":"1","key":"492_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1002\/jgt.22013","volume":"84","author":"M Bonamy","year":"2017","unstructured":"Bonamy, M., Kang, R.J.: List coloring with a bounded palette. Journal of Graph Theory 84(1), 93\u2013103 (2017)","journal-title":"Journal of Graph Theory"},{"key":"492_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms, Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"492_CR8","volume-title":"Graph Theory","author":"R Diestel","year":"2006","unstructured":"Diestel, R.: Graph Theory. Springer, Electronic library of mathematics (2006)"},{"key":"492_CR9","unstructured":"Erdos, P., Rubin, A.L., Taylor, H.: Choosability in graphs. In: Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium, vol. 26, pp. 125\u2013157 (1979)"},{"issue":"4","key":"492_CR10","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1002\/jgt.20057","volume":"48","author":"EM Eschen","year":"2005","unstructured":"Eschen, E.M., Ho\u00e0ng, C.T., Petrick, M.D., Sritharan, R.: Disjoint clique cutsets in graphs without long holes. Journal of Graph Theory 48(4), 277\u2013298 (2005)","journal-title":"Journal of Graph Theory"},{"issue":"2","key":"492_CR11","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.ic.2010.11.026","volume":"209","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fomin, F.V., Lokshtanov, D., Rosamond, F.A., Saurabh, S., Szeider, S., Thomassen, C.: On the complexity of some colorful problems parameterized by treewidth. Inf. Comput. 209(2), 143\u2013153 (2011)","journal-title":"Inf. Comput."},{"issue":"5","key":"492_CR12","doi-asserted-by":"publisher","first-page":"1941","DOI":"10.1137\/080742270","volume":"39","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Golovach, P.A., Lokshtanov, D., Saurabh, S.: Intractability of clique-width parameterizations. SIAM Journal on Computing 39(5), 1941\u20131956 (2010)","journal-title":"SIAM Journal on Computing"},{"key":"492_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F., Lokshtanov, D., Saurabh, S., Zehavi, M.: Kernelization: Theory of Parameterized Preprocessing: Theory of Parameterized Preprocessing. Cambridge University Press, United Kingdom (2019). Publisher Copyright: \u00a9 Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi 2019","DOI":"10.1017\/9781107415157"},{"issue":"4","key":"492_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.ipl.2012.12.003","volume":"113","author":"PA Golovach","year":"2013","unstructured":"Golovach, P.A., Heggernes, P., Hof, P., Paulusma, D.: Choosability on [CDATA[H]]$$H$$-free graphs. Information Processing Letters 113(4), 107\u2013110 (2013)","journal-title":"Information Processing Letters"},{"key":"492_CR15","doi-asserted-by":"crossref","unstructured":"Golovach, P.A., Heggernes, P.: Choosability of $$P_5$$[CDATA[P_5]]-free graphs. In: Mathematical Foundations of Computer Science 2009: 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings 34, pp. 382\u2013391 (2009). Springer","DOI":"10.1007\/978-3-642-03816-7_33"},{"key":"492_CR16","unstructured":"Golovach, P.A., Heggernes, P.: Choosability of $$P_5$$[CDATA[P_5]]-free graphs. Bulletin of the Syktyvkar University. Series 1. Mathematics. Mechanics. Computer science. (11), 126\u2013139 (2010)"},{"issue":"1\u20133","key":"492_CR17","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0012-365X(95)00104-5","volume":"159","author":"S Gutner","year":"1996","unstructured":"Gutner, S.: The complexity of planar graph choosability. Discrete Mathematics 159(1\u20133), 119\u2013130 (1996)","journal-title":"Discrete Mathematics"},{"issue":"8","key":"492_CR18","doi-asserted-by":"publisher","first-page":"2260","DOI":"10.1016\/j.disc.2008.04.061","volume":"309","author":"S Gutner","year":"2009","unstructured":"Gutner, S., Tarsi, M.: Some results on (a: b)-choosability. Discrete Mathematics 309(8), 2260\u20132270 (2009)","journal-title":"Discrete Mathematics"},{"key":"492_CR19","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/j.dam.2022.11.011","volume":"327","author":"L Jaffke","year":"2023","unstructured":"Jaffke, L., Jansen, B.M.: Fine-grained parameterized complexity analysis of graph coloring problems. Discrete Applied Mathematics 327, 33\u201346 (2023)","journal-title":"Discrete Applied Mathematics"},{"key":"492_CR20","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1016\/j.tcs.2019.08.006","volume":"795","author":"BM Jansen","year":"2019","unstructured":"Jansen, B.M., Nederlof, J.: Computing the chromatic number using graph decompositions via matrix rank. Theoretical Computer Science 795, 520\u2013539 (2019)","journal-title":"Theoretical Computer Science"},{"key":"492_CR21","unstructured":"Kowalik, L., Socala, A.: Tight lower bounds for list edge coloring. In: Eppstein, D. (ed.) 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018, June 18-20, 2018, Malm\u00f6, Sweden. LIPIcs, vol. 101, pp. 28\u201312812. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"issue":"3","key":"492_CR22","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1002\/jgt.20073","volume":"49","author":"D Kr\u00e1l\u2019","year":"2005","unstructured":"Kr\u00e1l\u2019, D., Sgall, J.: Coloring graphs from lists with bounded size of their union. Journal of Graph Theory 49(3), 177\u2013186 (2005)","journal-title":"Journal of Graph Theory"},{"key":"492_CR23","unstructured":"Marx, D., Mitsou, V.: Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth. (2016)"},{"key":"492_CR24","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1016\/j.jctb.2018.06.007","volume":"134","author":"M Molloy","year":"2019","unstructured":"Molloy, M.: The list chromatic number of graphs with small clique number. Journal of Combinatorial Theory, Series B 134, 264\u2013284 (2019)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"2","key":"492_CR25","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1002\/jgt.21819","volume":"79","author":"JA Noel","year":"2015","unstructured":"Noel, J.A., Reed, B.A., Wu, H.: A proof of a conjecture of ohba. Journal of Graph Theory 79(2), 86\u2013102 (2015)","journal-title":"Journal of Graph Theory"},{"issue":"1","key":"492_CR26","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s00493-005-0010-x","volume":"25","author":"B Reed","year":"2004","unstructured":"Reed, B., Sudakov, B.: List colouring when the chromatic number is close to the order of the graph. Combinatorica 25(1), 117\u2013123 (2004)","journal-title":"Combinatorica"},{"issue":"3","key":"492_CR27","first-page":"10","volume":"29","author":"VG Vizing","year":"1976","unstructured":"Vizing, V.G.: Coloring the vertices of a graph in prescribed colors. Diskret. Analiz 29(3), 10 (1976)","journal-title":"Diskret. Analiz"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00492-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00492-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00492-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T11:42:36Z","timestamp":1750160556000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00492-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,30]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["492"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00492-0","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2025,5,30]]},"assertion":[{"value":"15 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 May 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no conflicts of interest to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"24"}}