@inproceedings{e5d98766cd71426d87f5d70b764dc533,
title = "Combinatorial proof that subprojective constraint satisfaction problems are NP-complete",
abstract = "We introduce a new general polynomial-time construction-the fibre construction- which reduces any constraint satisfaction problem CSP(ℋ) to the constraint satisfaction problem CSP(P), where P is any subprojective relational structure. As a consequence we get a new proof (not using universal algebra) that CSP(P) is NP-complete for any subprojective (and thus also projective) relational structure. This provides a starting point for a new combinatorial approach to the NP-completeness part of the conjectured Dichotomy Classification of CSPs, which was previously obtained by algebraic methods. This approach is flexible enough to yield NP-completeness of coloring problems with large girth and bounded degree restrictions.",
author = "Jaroslav Ne{\v s}et{\v r}il and Mark Siggers",
year = "2007",
doi = "10.1007/978-3-540-74456-6_16",
language = "English",
isbn = "9783540744559",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "159--170",
booktitle = "Mathematical Foundations of Computer Science 2007 - 32nd International Symposium, MFCS 2007, Proceedings",
address = "Germany",
note = "32nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2007 ; Conference date: 26-08-2007 Through 31-08-2007",
}