Marx, Dániel ;
Mitsou, Valia
DoubleExponential and TripleExponential Bounds for Choosability Problems Parameterized by Treewidth
Abstract
Choosability, introduced by Erdös, Rubin, and Taylor [Congr. Number. 1979], is a wellstudied concept in graph theory: we say that a graph is cchoosable 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 3choosability 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 doubleexponential 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 ExponentialTime Hypothesis (ETH). We consider also the optimization problem where the task is to delete the minimum number of vertices to make the graph 4choosable, 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.
BibTeX  Entry
@InProceedings{marx_et_al:LIPIcs:2016:6307,
author = {D{\'a}niel Marx and Valia Mitsou},
title = {{DoubleExponential and TripleExponential Bounds for Choosability Problems Parameterized by Treewidth}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {28:128:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6307},
URN = {urn:nbn:de:0030drops63078},
doi = {10.4230/LIPIcs.ICALP.2016.28},
annote = {Keywords: Parameterized Complexity, List coloring, Treewidth, Lower bounds under ETH}
}
2016
Keywords: 

Parameterized Complexity, List coloring, Treewidth, Lower bounds under ETH 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 