2026-07-20T10:52:10Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6307 2024-03-06T10:37:41Z ddc:004 open_access

Double-Exponential and Triple-Exponential Bounds for Choosability Problems Parameterized by Treewidth Marx, Dániel Mitsou, Valia Parameterized Complexity List coloring Treewidth Lower bounds under ETH Choosability, introduced by Erdös, Rubin, and Taylor [Congr. Number. 1979], is a well-studied concept in graph theory: we say that a graph is c-choosable if for any assignment of a list of c colors to each vertex, there is a proper coloring where each vertex uses a color from its list. We study the complexity of deciding choosability on graphs of bounded treewidth. It follows from earlier work that 3-choosability can be decided in time 2^(2^(O(w)))*n^(O(1)) on graphs of treewidth w. We complement this result by a matching lower bound giving evidence that double-exponential dependence on treewidth may be necessary for the problem: we show that an algorithm with running time 2^(2^(o(w)))*n^(O(1)) would violate the Exponential-Time Hypothesis (ETH). We consider also the optimization problem where the task is to delete the minimum number of vertices to make the graph 4-choosable, and demonstrate that dependence on treewidth becomes tripleexponential for this problem: it can be solved in time 2^(2^(2^(O(w))))*n^(O(1)) on graphs of treewidth w, but an algorithm with running time 2^(2^(2^(o(w))))*n^(O(1)) would violate ETH. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dániel Marx and Valia Mitsou 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.28 urn:nbn:de:0030-drops-63078 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.28 eng https://creativecommons.org/licenses/by/3.0/legalcode