The complexity of the list homomorphism problem for graphs (Q693060): Difference between revisions

This very dense and high-level article aims at completely classifying the computational complexity of the list H-colouring problem, a rather famous graph problem. A certain number of pre-requisites, at different levels, are necessary for the reader to be able to understand the contents of the paper: graphs, graph colouring, graph homomorphism; complexity classes (beyond the usual NP-completeness), such as NL- or L-completeness; first-order logic; constraint satisfaction problems. Some other advanced notions and terms are also needed to be known -- the paper is not self-contained in that sense. Altogether, this paper is not for the faint-hearted. That said, the paper, although very dense in terms of results, is clearly written, and its somewhat complicated structure is very clearly described in its first few pages. More importantly, its results cover a wide spectrum, and altogether lead to a strong paper.