@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",

}