Autor:	Egri, Laszlo, Krokhin, Andrei, Larose, Benoit, Tesson, Pascal
Rok vydání:	2009
Předmět:	Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	We completely classify the computational complexity of the list H-colouring problem for graphs (with possible loops) in combinatorial and algebraic terms: for every graph H the problem is either NP-complete, NL-complete, L-complete or is first-order definable; descriptive complexity equivalents are given as well via Datalog and its fragments. Our algebraic characterisations match important conjectures in the study of constraint satisfaction problems. Comment: 12 pages, STACS 2010
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/0912.3802 Zobrazit plný text záznamu View this record from Arxiv