The complexity of the list homomorphism problem for graphs

László Egri 1, * Andrei Krokhin 2 Benoit Larose 3 Pascal Tesson 4
* Corresponding author
1 SOCS - School of Computer Science [Quebec]
2 School of Engineering and Computing Sciences
3 Department of Mathematics and Statistics
4 Department of Computer Science
Abstract : 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.
Keywords : graph homomorphism constraint satisfaction problem complexity universal algebra Datalog
Document type :
Conference papers
Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.335-346, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science
Liste complète des métadonnées
https://hal.inria.fr/inria-00455321
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 10:15:49 AM
Last modification on : Wednesday, February 10, 2010 - 10:39:30 AM
Document(s) archivé(s) le : Friday, June 18, 2010 - 7:50:40 PM

File

egri.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00455321, version 1

Collections

STACS2010

Citation

László Egri, Andrei Krokhin, Benoit Larose, Pascal Tesson. The complexity of the list homomorphism problem for graphs. Jean-Yves Marion and Thomas Schwentick. 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, Mar 2010, Nancy, France. pp.335-346, 2010, Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science. <inria-00455321>

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

169

Document downloads

177

Contact


archive-ouverte@inria.fr