{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:39Z","timestamp":1725488979520},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74456-6_16","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"159-170","source":"Crossref","is-referenced-by-count":1,"title":["Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete"],"prefix":"10.1007","author":[{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"first","affiliation":[]},{"given":"Mark","family":"Siggers","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Bodnar\u010duk, V.G., Kaluzhnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras I - II (in Russian), Kibernetika, 3 (1969), 1-10 and 5 (1969), 1-9. English version: Cybernetics, 243-252 and 531-539 (1969)","DOI":"10.1007\/BF01267873"},{"key":"16_CR2","doi-asserted-by":"crossref","unstructured":"Bulatov, A.: A dichotomy theorem for constraints on a three element set. FOCS 2002, 649\u2013658 (2002)","DOI":"10.1109\/SFCS.2002.1181990"},{"key":"16_CR3","unstructured":"Bulatov, A.: Tractable conservative Constraint Satisfaction Problems, ACM Trans. on Comp. Logic. LICS 2003, 321\u2013330 (2003)"},{"issue":"1","key":"16_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2005.09.028","volume":"349","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A.: H-Coloring Dichotomy Revisited. Theoret. Comp. Sci.\u00a0349(1), 31\u201339 (2005)","journal-title":"Theoret. Comp. Sci."},{"issue":"3","key":"16_CR5","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM J. Comput.\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM J. Comput."},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-45022-X_24","volume-title":"Automata, Languages and Programming","author":"A. Bulatov","year":"2000","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Constraint satisfaction problems and finite algebras. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 272\u2013282. Springer, Heidelberg (2000)"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications, SIAM\u00a0 (2001)","DOI":"10.1137\/1.9780898718546"},{"key":"16_CR8","unstructured":"Feder, T., Hell, P., Huang, J.: List Homomorphisms of Graphs with Bounded Degree (submitted)"},{"issue":"1","key":"16_CR9","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"Feder, T., Vardi, M.: The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM J. Comput.\u00a028(1), 57\u2013104 (1999)","journal-title":"SIAM J. Comput."},{"key":"16_CR10","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D. Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pacific. Journal of Math.\u00a027, 95\u2013100 (1968)","journal-title":"Pacific. Journal of Math."},{"key":"16_CR11","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1017\/CBO9781107359970.008","volume-title":"Survey in Combinatorics 2003","author":"P. Hell","year":"2003","unstructured":"Hell, P.: Algorithmic aspects of graph homomorphisms. In: Survey in Combinatorics 2003, pp. 239\u2013276. Cambridge University Press, Cambridge (2003)"},{"key":"16_CR12","first-page":"407","volume-title":"Topics in Discrete Mathematics. Dedicated to Jarik Nesetril on the Occasion of his 60th Birthday","author":"P. Hell","year":"2006","unstructured":"Hell, P.: From Graph Colouring to Constraint Satisfaction: There and Back Again. In: Klazar, M., Kratochvil, J., Loebl, M., Matousek, J., Thomas, R., Valtr, P. (eds.) Topics in Discrete Mathematics. Dedicated to Jarik Nesetril on the Occasion of his 60th Birthday, pp. 407\u2013432. Springer, Heidelberg (2006)"},{"key":"16_CR13","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(90)90132-J","volume":"48","author":"P. Hell","year":"1990","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: On the complexity of H-colouring. J. Combin. Theory B\u00a048, 92\u2013100 (1990)","journal-title":"J. Combin. Theory B"},{"key":"16_CR14","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphisms","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphisms. Oxford University Press, Oxford (2004)"},{"issue":"1-2","key":"16_CR15","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(97)00230-2","volume":"200","author":"P.G. Jeavons","year":"1998","unstructured":"Jeavons, P.G.: On the algebraic structure of combinatorial problems. Theoret. Comput. Sci.\u00a0200(1-2), 185\u2013204 (1998)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR16","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P.G. Jeavons","year":"1997","unstructured":"Jeavons, P.G., Cohen, D.A., Gyssens, M.: Closure properties of Constraints. Journal of the ACM\u00a044, 527\u2013548 (1997)","journal-title":"Journal of the ACM"},{"issue":"1-3","key":"16_CR17","first-page":"257","volume":"233","author":"A. Kostochka","year":"2001","unstructured":"Kostochka, A., Ne\u0161et\u0159il, J., Smol\u00edkov\u00e1, P.: Colorings and homomorphisms of degenerate and bounded degree graphs. Graph theory (Prague, 1998). Discrete Math\u00a0233(1-3), 257\u2013276 (2001)","journal-title":"Graph theory (Prague, 1998). Discrete Math"},{"issue":"1","key":"16_CR18","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1137\/S0895480101389478","volume":"17","author":"B. Larose","year":"2003","unstructured":"Larose, B., Z\u00e1dori, L.: The Complexity of the Extendibility Problem for Finite Posets. SIAM J. Discrete Math.\u00a017(1), 114\u2013121 (2003)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"16_CR19","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/S0097539703435492","volume":"36","author":"T. \u0141uczak","year":"2006","unstructured":"\u0141uczak, T., Ne\u0161et\u0159il, J.: A probabilistic approach to the dichotomy problem. SIAM J. Comput.\u00a036(3), 835\u2013843 (2006)","journal-title":"SIAM J. Comput."},{"key":"16_CR20","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"Montanari, U.: Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences\u00a07, 95\u2013132 (1974)","journal-title":"Information Sciences"},{"key":"16_CR21","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(79)90121-3","volume":"26","author":"V. M\u00fcller","year":"1979","unstructured":"M\u00fcller, V.: On colorings of graphs without short cycles. Discrete Math.\u00a026, 165\u2013176 (1979)","journal-title":"Discrete Math."},{"key":"16_CR22","first-page":"122","volume":"46","author":"J. Ne\u0161et\u0159il","year":"1989","unstructured":"Ne\u0161et\u0159il, J., R\u00f6dl, V.: Chromatically optimal rigid graphs. J. Comb. Th. B\u00a046, 122\u2013141 (1989)","journal-title":"J. Comb. Th. B"},{"key":"16_CR23","unstructured":"Ne\u0161et\u0159il, J., Siggers, M.: A New Combinatorial Approach to the CSP Dichotomy Classification (submitted, 2007)"},{"issue":"1","key":"16_CR24","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/j.jctb.2003.06.001","volume":"90","author":"J. Ne\u0161et\u0159il","year":"2004","unstructured":"Ne\u0161et\u0159il, J., Zhu, X.: On sparse graphs with given colorings and homomorphisms. J. Combin. Theory Ser. B\u00a090(1), 161\u2013172 (2004)","journal-title":"J. Combin. Theory Ser. B"},{"key":"16_CR25","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"16_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relatrionenalgebren","author":"R. P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relatrionenalgebren. DVW, Berlin (1979)"},{"key":"16_CR27","unstructured":"McKenzie, R.: Personal Communication"},{"key":"16_CR28","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the 10th ACM Symposium on Theory of Computing (STOC 1978), pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"16_CR29","unstructured":"Siggers, M.: On Highly Ramsey Infinte Graphs. (submitted, 2006)"},{"key":"16_CR30","unstructured":"Siggers, M.: Dichotomy for Bounded Degree H-colouring (submitted, 2007)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_16.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T10:28:40Z","timestamp":1619519320000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}