{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T05:14:29Z","timestamp":1790745269758,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476710","type":"print"},{"value":"9783662476727","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_39","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"481-493","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Lower Bounds for the Graph Homomorphism Problem"],"prefix":"10.1007","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Golovnev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"6","key":"39_CR1","doi-asserted-by":"publisher","first-page":"2430","DOI":"10.1137\/070711670","volume":"39","author":"P Austrin","year":"2010","unstructured":"Austrin, P.: Towards sharp inapproximability for any 2-CSP. SIAM J. Comput. 39(6), 2430\u20132463 (2010)","journal-title":"SIAM J. Comput."},{"key":"39_CR2","doi-asserted-by":"crossref","unstructured":"Barto, L., Kozik, M., Niven, T.: Graphs, polymorphisms and the complexity of homomorphism problems. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 789\u2013796 (2008)","DOI":"10.1145\/1374376.1374488"},{"issue":"2","key":"39_CR3","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion-exclusion. SIAM J. Computing 39(2), 546\u2013563 (2009)","journal-title":"SIAM J. Computing"},{"issue":"8","key":"39_CR4","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Computer and System Sciences 72(8), 1346\u20131367 (2006)","journal-title":"J. Computer and System Sciences"},{"issue":"40\u201342","key":"39_CR5","doi-asserted-by":"publisher","first-page":"3736","DOI":"10.1016\/j.tcs.2010.06.026","volume":"411","author":"J Chen","year":"2010","unstructured":"Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theoretical Computer Science 411(40\u201342), 3736\u20133756 (2010)","journal-title":"Theoretical Computer Science"},{"key":"39_CR6","doi-asserted-by":"crossref","unstructured":"Cygan, M., Fomin, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer (2015)","DOI":"10.1007\/978-3-319-21275-3"},{"key":"39_CR7","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/S0304-3975(02)00017-8","volume":"281","author":"J Diaz","year":"2002","unstructured":"Diaz, J., Serna, M., Thilikos, D.M.: Counting $$H$$-colorings of partial $$k$$-trees. Theoretical Computer Science 281, 291\u2013309 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"39_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T Feder","year":"1998","unstructured":"Feder, T., Vardi, M.Y.: The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput. 28(1), 57\u2013104 (1998)","journal-title":"SIAM J. Comput."},{"key":"39_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-540-70575-8_25","volume-title":"Automata, Languages and Programming","author":"J Fiala","year":"2008","unstructured":"Fiala, J., Golovach, P.A., Kratochv\u00edl, J.: Computational complexity of the distance constrained labeling problem for trees (extended abstract). In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 294\u2013305. Springer, Heidelberg (2008)"},{"issue":"2","key":"39_CR10","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/j.cosrev.2008.06.001","volume":"2","author":"J Fiala","year":"2008","unstructured":"Fiala, J., Kratochv\u00edl, J.: Locally constrained graph homomorphisms - structure, complexity, and applications. Computer Science Review 2(2), 97\u2013111 (2008)","journal-title":"Computer Science Review"},{"issue":"2","key":"39_CR11","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/s00224-007-2007-x","volume":"41","author":"FV Fomin","year":"2007","unstructured":"Fomin, F.V., Heggernes, P., Kratsch, D.: Exact algorithms for graph homomorphisms. Theory of Computing Systems 41(2), 381\u2013393 (2007)","journal-title":"Theory of Computing Systems"},{"key":"39_CR12","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer (2010)","DOI":"10.1007\/978-3-642-16533-7"},{"key":"39_CR13","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman (1979)"},{"issue":"4","key":"39_CR14","doi-asserted-by":"publisher","first-page":"586","DOI":"10.1137\/0405048","volume":"5","author":"JR Griggs","year":"1992","unstructured":"Griggs, J.R., Yeh, R.K.: Labelling graphs with a condition at distance 2. SIAM J. Discrete Math. 5(4), 586\u2013595 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"39_CR15","doi-asserted-by":"crossref","unstructured":"Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. J. ACM 54(1) (2007)","DOI":"10.1145\/1206035.1206036"},{"issue":"2","key":"39_CR16","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/s00453-009-9302-7","volume":"59","author":"F Havet","year":"2011","unstructured":"Havet, F., Klazar, M., Kratochv\u00edl, J., Kratsch, D., Liedloff, M.: Exact algorithms for L(2, 1)-labeling of graphs. Algorithmica 59(2), 169\u2013194 (2011)","journal-title":"Algorithmica"},{"issue":"1","key":"39_CR17","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$$-coloring. J. Combinatorial Theory Ser. B 48(1), 92\u2013110 (1990)","journal-title":"J. Combinatorial Theory Ser. B"},{"key":"39_CR18","series-title":"Oxford Lecture Series in Mathematics and its Applications","doi-asserted-by":"publisher","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 Lecture Series in Mathematics and its Applications, vol. 28. Oxford University Press, Oxford (2004)"},{"issue":"4","key":"39_CR19","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. J. Computer and System Sciences 63(4), 512\u2013530 (2001)","journal-title":"J. Computer and System Sciences"},{"key":"39_CR20","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2012.06.037","volume":"505","author":"K Junosza-Szaniawski","year":"2013","unstructured":"Junosza-Szaniawski, K., Kratochv\u00edl, J., Liedloff, M., Rossmanith, P., Rzazewski, P.: Fast exact algorithm for l(2, 1)-labeling of graphs. Theor. Comput. Sci. 505, 42\u201354 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"39_CR21","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/0020-0190(76)90065-X","volume":"5","author":"EL Lawler","year":"1976","unstructured":"Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5(3), 66\u201367 (1976)","journal-title":"Inf. Process. Lett."},{"key":"39_CR22","unstructured":"Lokshtanov, D.: Private communication (2014)"},{"key":"39_CR23","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Slightly superexponential parameterized problems. In: Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 760\u2013776. SIAM (2011)","DOI":"10.1137\/1.9781611973082.60"},{"key":"39_CR24","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bulletin of EATCS 3(105) (2013)"},{"key":"39_CR25","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L.: Large networks and graph limits, vol. 60. American Mathematical Soc. (2012)","DOI":"10.1090\/coll\/060"},{"issue":"1","key":"39_CR26","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory of Computing 6(1), 85\u2013112 (2010)","journal-title":"Theory of Computing"},{"key":"39_CR27","doi-asserted-by":"crossref","unstructured":"Raghavendra, P.: Optimal algorithms and inapproximability results for every CSP? In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 245\u2013254 (2008)","DOI":"10.1145\/1374376.1374414"},{"issue":"7","key":"39_CR28","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1016\/j.ipl.2014.02.012","volume":"114","author":"P Rza\u017cewski","year":"2014","unstructured":"Rza\u017cewski, P.: Exact algorithm for graph homomorphism and locally injective graph homomorphism. Inf. Process. Lett. 114(7), 387\u2013391 (2014)","journal-title":"Inf. Process. Lett."},{"key":"39_CR29","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Cengage Learning (2005)"},{"key":"39_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/978-3-540-79723-4_18","volume-title":"Parameterized and Exact Computation","author":"P Traxler","year":"2008","unstructured":"Traxler, P.: The time complexity of constraint satisfaction. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 190\u2013201. Springer, Heidelberg (2008)"},{"key":"39_CR31","unstructured":"Wahlstr\u00f6m, M.: Problem 5.21. time complexity of graph homomorphism. In: Thore Husfeldt, Dieter Kratsch, R.P., Sorkin, G. (eds.) Exact Complexity of NP-Hard Problems. Dagstuhl Seminar 10441 Final Report. Dagstuhl (2010)"},{"issue":"2","key":"39_CR32","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/s00224-010-9261-z","volume":"49","author":"M Wahlstr\u00f6m","year":"2011","unstructured":"Wahlstr\u00f6m, M.: New plain-exponential time classes for graph homomorphism. Theory of Computing Systems 49(2), 273\u2013282 (2011)","journal-title":"Theory of Computing Systems"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_39","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:13:38Z","timestamp":1676945618000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_39"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_39","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}