The complexity of the list homomorphism problem for graphs

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.
Type de document :
Communication dans un congrès
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
Contributeur : Publications Loria <>
Soumis le : mercredi 10 février 2010 - 10:15:49
Dernière modification le : lundi 16 octobre 2017 - 17:00:20
Document(s) archivé(s) le : vendredi 18 juin 2010 - 19:50:40

Fichier

egri.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00455321, version 1

Collections

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〉

Partager

Métriques

Consultations de la notice

173

Téléchargements de fichiers

199