Accéder aux actualités Evènements des groupes Liste des groupes publics
Evènement pour le groupe Séminaire Méthodes Formelles

 Date 2016-07-05  11:00-12:00 Titre Double-exponential and triple-exponential bounds for choosability problems parameterized by treewidth Résumé Choosability, introduced by Erdos, 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 triple-exponential 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. The significance of the results is that these problems are apparently the first fairly natural graph-theoretic problems that require double-exponential or triple-exponential dependence on treewidth. Joint work with Dániel Marx. Lieu 178 Orateur Valia Mitsou Email http://info.ilab.sztaki.hu/~vmitsou/ Url MTA SZTAKI

Aucun document lié à cet événement.

Retour
Retour à l'index