{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T10:40:20Z","timestamp":1737369620821,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"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_17","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T07:29:48Z","timestamp":1187076588000},"page":"171-181","source":"Crossref","is-referenced-by-count":2,"title":["NP by Means of Lifts and Shadows"],"prefix":"10.1007","author":[{"given":"G\u00e1bor","family":"Kun","sequence":"first","affiliation":[]},{"given":"Jaroslav","family":"Ne\u0161et\u0159il","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Atserias, A.: On Digraph Coloring Problems and Treewidth Duality. In: 20th IEEE Symposium on Logic in Computer Science (LICS), pp. 106\u2013115 (2005)","DOI":"10.1109\/LICS.2005.31"},{"issue":"2","key":"17_CR2","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1145\/1131342.1131344","volume":"53","author":"A. Atserias","year":"2006","unstructured":"Atserias, A., Dawar, A., Kolaitis, P.G.: On Preservation under Homomorphisms and Conjunctive Queries. Journal of the ACM\u00a053(2), 208\u2013237 (2006)","journal-title":"Journal of the ACM"},{"key":"17_CR3","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0012-365X(86)90065-8","volume":"59","author":"P. Erd\u0151s","year":"1986","unstructured":"Erd\u0151s, P., F\u00fcredi, Z., Hajnal, A., Komj\u00e1th, P., R\u00f6dl, V., Seress, \u00c1.: Coloring graphs with locally few colors. Discrete Math\u00a059, 21\u201334 (1986)","journal-title":"Discrete Math"},{"key":"17_CR4","unstructured":"Fagin, R.: Generalized first-order spectra and polynomial-time recognizable sets. In: Karp, R. (ed.) Complexity of Computation, SIAM-AMS Proceedings, vol.\u00a07, pp. 43\u201373 (1974)"},{"issue":"1","key":"17_CR5","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":"17_CR6","doi-asserted-by":"crossref","unstructured":"Foniok, J., Ne\u0161et\u0159il, J., Tardif, C.: Generalized dualities and maximal finite antichains in the homomorphism order of relational structures. In: KAM-DIMATIA Series 2006-766 (to appear in European J. Comb.)","DOI":"10.1007\/11917496_3"},{"issue":"6","key":"17_CR7","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1002\/malq.19770233608","volume":"23","author":"P. G\u00e1cs","year":"1977","unstructured":"G\u00e1cs, P., Lov\u00e1sz, L.: Some remarks on generalized spectra. Z. Math. Log. Grdl.\u00a023(6), 547\u2013554 (1977)","journal-title":"Z. Math. Log. Grdl."},{"key":"17_CR8","doi-asserted-by":"crossref","unstructured":"Feder, T., Hell, P., Klein, S., Motwani, R.: Complexity of graph partition problems. In: 31st Annual ACM STOC, pp. 464\u2013472 (1999)","DOI":"10.1145\/301250.301373"},{"key":"17_CR9","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001","volume-title":"Graphs and Homomorphism","author":"P. Hell","year":"2004","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: Graphs and Homomorphism. Oxford University Press, Oxford (2004)"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"Immerman, N.: Languages that capture complexity classes. SIAM J. Comput.\u00a016, 760\u2013778 (1987)","journal-title":"SIAM J. Comput."},{"key":"17_CR11","unstructured":"Kun, G.: On the complexity of Constraint Satisfaction Problem, PhD thesis (in Hungarian) (2006)"},{"key":"17_CR12","unstructured":"Kun, G.: Constraints, MMSNP and expander structures, Combinatorica (submitted, 2007)"},{"key":"17_CR13","unstructured":"Kun, G., Ne\u0161et\u0159il, J.: Forbidden lifts (NP and CSP for combinatorists). In: KAM-DIMATIA Series 2006-775 (to appear in European J. Comb.)"},{"issue":"1","key":"17_CR14","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: On the structure of Polynomial Time Reducibility. Journal of the ACM\u00a022(1), 155\u2013171 (1975)","journal-title":"Journal of the ACM"},{"issue":"3","key":"17_CR15","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/S0097539703435492","volume":"36","author":"T. Luczak","year":"2006","unstructured":"Luczak, T., Ne\u0161et\u0159il, J.: A probabilistic approach to the dichotomy problem. SIAM J. Comp.\u00a036(3), 835\u2013843 (2006)","journal-title":"SIAM J. Comp."},{"key":"17_CR16","unstructured":"Madelaine, F.: Constraint satisfaction problems and related logic, PhD thesis (2003)"},{"key":"17_CR17","unstructured":"Madelaine, F., Stewart, I.A.: Constraint satisfaction problems and related logic, (manuscript, 2005)"},{"key":"17_CR18","unstructured":"Matou\u0161ek, J., Ne\u0161et\u0159il, J.: Constructions of sparse graphs with given homomorphisms (to appear)"},{"key":"17_CR19","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1016\/0012-365X(78)90062-6","volume":"22","author":"J. Ne\u0161et\u0159il","year":"1978","unstructured":"Ne\u0161et\u0159il, J., Pultr, A.: On classes of relations and graphs determined by subobjects and factorobjects. Discrete Math.\u00a022, 287\u2013300 (1978)","journal-title":"Discrete Math."},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1145\/1132516.1132575","volume-title":"STOC 2006, Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"J. Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Low tree-width decompositions and algorithmic consequences. In: STOC 2006, Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pp. 391\u2013400. ACM Press, New York (2006)"},{"key":"17_CR21","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Grad and Classes with bounded expansion III. - Restricted Dualities, KAM-DIMATIA Series 2005-741 (to appear in European J. Comb.)"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0095-8956(89)90039-7","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, 133\u2013141 (1989)","journal-title":"J. Comb. Th. B"},{"key":"17_CR23","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1006\/jctb.2000.1970","volume":"80","author":"J. Ne\u0161et\u0159il","year":"2000","unstructured":"Ne\u0161et\u0159il, J., Tardif, C.: Duality theorems for finite structures (characterising gaps and good characterization. J. Combin. Theory\u00a0B\u00a080, 80\u201397 (2000)","journal-title":"J. Combin. Theory\u00a0B"},{"issue":"1","key":"17_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. Comb. Th. B\u00a090(1), 161\u2013172 (2004)","journal-title":"J. Comb. Th. B"},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"Rossman, B.: Existential positive types and preservation under homomorphisms. In: 20th IEEE Symposium on Logic in Computer Science (LICS 2005), pp. 467\u2013476 (2005)","DOI":"10.1109\/LICS.2005.16"},{"key":"17_CR26","first-page":"589","volume":"26","author":"G. Simonyi","year":"2006","unstructured":"Simonyi, G., Tardos, G.: Local chromatic number, Ky Fan\u2019s theorem and circular colorings. Combinatorica\u00a026, 589\u2013626 (2006)","journal-title":"Combinatorica"},{"key":"17_CR27","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages. In: Proceedings of 14th ACM Symposium on Theory of Computing\u00a0 pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"}],"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_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T09:36:58Z","timestamp":1737365818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540744559","9783540744566"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}