| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
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.
https://hal.inria.fr/inria-00455321
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 10:15:49 AM
Last modification on : Monday, July 20, 2020 - 1:06:04 PM
Long-term archiving on: : Friday, June 18, 2010 - 7:50:40 PM
Contributor : Publications Loria <>
Submitted on : Wednesday, February 10, 2010 - 10:15:49 AM
Last modification on : Monday, July 20, 2020 - 1:06:04 PM
Long-term archiving on: : Friday, June 18, 2010 - 7:50:40 PM
File
egri.pdf
Files produced by the author(s)