The complexity of the list homomorphism problem for graphs

László Egri; Andrei Krokhin; Benoit Larose; Pascal Tesson

The complexity of the list homomorphism problem for graphs

László Egri ^{1, *} Andrei Krokhin ² Benoit Larose ³ Pascal Tesson ⁴

* 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

Domain :

Computer Science [cs] / Computational Complexity [cs.CC]

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 : Thursday, July 26, 2018 - 2:08:02 PM
Document(s) archivé(s) le : Friday, June 18, 2010 - 7:50:40 PM

egri.pdf

Files produced by the author(s)

The complexity of the list homomorphism problem for graphs

File

Identifiers

Collections

Citation

Export

Metrics

180

215

Contact

The complexity of the list homomorphism problem for graphs

File

Identifiers

Collections

Citation

Export

Share

Metrics

180

215

Contact