{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T10:28:22Z","timestamp":1742639302179,"version":"3.37.3"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T00:00:00Z","timestamp":1529107200000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Government of the Russian Federation","award":["14.Z50.31.0030"]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1319051 and CCF-1065106"],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"National Science Centre of Poland","doi-asserted-by":"crossref","award":["UMO-2013\/09\/B\/ST6\/03136"],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2017,6,30]]},"abstract":"\n We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph\n G<\/jats:italic>\n to graph\n H<\/jats:italic>\n cannot be done in time |\n V<\/jats:italic>\n (\n H<\/jats:italic>\n )|\n \n o<\/jats:italic>\n (|\n V<\/jats:italic>\n (\n G<\/jats:italic>\n )|)\n <\/jats:sup>\n . We also show an exponential-time reduction from Graph Homomorphism to Subgraph Isomorphism. This rules out (subject to ETH) a possibility of |\n V<\/jats:italic>\n (\n H<\/jats:italic>\n )|\n \n o<\/jats:italic>\n (|\n V<\/jats:italic>\n (\n H<\/jats:italic>\n )|)\n <\/jats:sup>\n -time algorithm deciding if graph\n G<\/jats:italic>\n is a subgraph of\n H<\/jats:italic>\n . For both problems our lower bounds asymptotically match the running time of brute-force algorithms trying all possible mappings of one graph into another. Thus, our work closes the gap in the known complexity of these fundamental problems.\n <\/jats:p>\n Moreover, as a consequence of our reductions, conditional lower bounds follow for other related problems such as Locally Injective Homomorphism, Graph Minors, Topological Graph Minors, Minimum Distortion Embedding and Quadratic Assignment Problem.<\/jats:p>","DOI":"10.1145\/3051094","type":"journal-article","created":{"date-parts":[[2017,6,16]],"date-time":"2017-06-16T18:10:59Z","timestamp":1497636659000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Tight Lower Bounds on Graph Embedding Problems"],"prefix":"10.1145","volume":"64","author":[{"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warszawa, Poland"}]},{"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[{"name":"University of Bergen; St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, Bergen, Norway"}]},{"given":"Alexander","family":"Golovnev","sequence":"additional","affiliation":[{"name":"New York University; St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, NY, USA"}]},{"given":"Alexander S.","family":"Kulikov","sequence":"additional","affiliation":[{"name":"St. Petersburg Department of Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia"}]},{"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[{"name":"University of California-San Diego, CA, U.S.A"}]},{"given":"Jakub","family":"Pachocki","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, PA, USA"}]},{"given":"Arkadiusz","family":"Soca\u0142a","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Warszawa, Poland"}]}],"member":"320","published-online":{"date-parts":[[2017,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/100789403"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958033.1958048"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060624"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"B\u0103doiu Mihai","year":"2005","unstructured":"Mihai B\u0103doiu , Kedar Dhamdhere , Anupam Gupta , Yuri Rabinovich , Harald R\u00e4cke , R. Ravi , and Anastasios Sidiropoulos . 2005 b. Approximation algorithms for low-distortion embeddings into low-dimensional spaces . In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905) . SIAM, 119--128. Mihai B\u0103doiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald R\u00e4cke, R. Ravi, and Anastasios Sidiropoulos. 2005b. Approximation algorithms for low-distortion embeddings into low-dimensional spaces. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). SIAM, 119--128."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374488"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/1061279.1712328"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-010-9460-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.04.007"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Marek Cygan Fedor Fomin Bart M. P. Jansen \u0141ukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Micha\u0142 Pilipczuk and Saket Saurabh. 2014. School on Parameterized Algorithms and Complexity\u2014Open Problems. Retrieved from http:\/\/fptschool.mimuw.edu.pl\/opl.pdf. Marek Cygan Fedor Fomin Bart M. P. Jansen \u0141ukasz Kowalik Daniel Lokshtanov D\u00e1niel Marx Marcin Pilipczuk Micha\u0142 Pilipczuk and Saket Saurabh. 2014. School on Parameterized Algorithms and Complexity\u2014Open Problems. Retrieved from http:\/\/fptschool.mimuw.edu.pl\/opl.pdf.","DOI":"10.1007\/978-3-319-21275-3"},{"volume-title":"Parameterized Algorithms","author":"Cygan Marek","key":"e_1_2_1_12_1","unstructured":"Marek Cygan , Fedor V. Fomin , \u0141ukasz Kowalik , D\u00e1niel Lokshtanov , Daniel Marx , Marcin Pilipczuk , Micha\u0142 Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, \u0141ukasz Kowalik, D\u00e1niel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Micha\u0142 Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.10.032"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/645900.672601"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489789"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_25"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.06.001"},{"key":"e_1_2_1_19_1","unstructured":"Fedor Fomin Kazuo Iwama and Dieter Kratsch. 2008. Moderately exponential time algorithms (dagstuhl seminar 08431). In Dagstuhl Reports. Retrieved from http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1798\/pdf\/08431.SWM.Paper.1798.pdf. 1. Fedor Fomin Kazuo Iwama and Dieter Kratsch. 2008. Moderately exponential time algorithms (dagstuhl seminar 08431). In Dagstuhl Reports. Retrieved from http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2008\/1798\/pdf\/08431.SWM.Paper.1798.pdf. 1."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-2007-x"},{"key":"e_1_2_1_21_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch . 2010 . Exact Exponential Algorithms. Springer . Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.02.043"},{"key":"e_1_2_1_23_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405048"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118734.3118821"},{"key":"e_1_2_1_27_1","first-page":"196","article-title":"A dynamic programming approach to sequencing problems","volume":"10","author":"Held Michael","year":"1962","unstructured":"Michael Held and Richard M. Karp . 1962 . A dynamic programming approach to sequencing problems . J. SIAM 10 (1962), 196 -- 210 . Michael Held and Richard M. Karp. 1962. A dynamic programming approach to sequencing problems. J. SIAM 10 (1962), 196--210.","journal-title":"J. SIAM"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"volume-title":"Oxford Lecture Series in Mathematics and its Applications","author":"Hell Pavol","key":"e_1_2_1_29_1","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il . 2004. Graphs and Homomorphisms . Oxford Lecture Series in Mathematics and its Applications , Vol. 28 . Oxford University Press , Oxford . Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications, Vol. 28. Oxford University Press, Oxford."},{"key":"e_1_2_1_30_1","unstructured":"Thore Husfeldt Ramamohan Paturi Gregory B. Sorkin and Ryan Williams. 2013. Exponential algorithms: Algorithms and complexity beyond polynomial time (dagstuhl seminar 13331). In Dagstuhl Reports. Retrieved from http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2013\/4342\/pdf\/dagrep_v003_i008_p040_s13331.pdf. 63. Thore Husfeldt Ramamohan Paturi Gregory B. Sorkin and Ryan Williams. 2013. Exponential algorithms: Algorithms and complexity beyond polynomial time (dagstuhl seminar 13331). In Dagstuhl Reports. Retrieved from http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2013\/4342\/pdf\/dagrep_v003_i008_p040_s13331.pdf. 63."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.037"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1958014"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90065-X"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.10.003"},{"key":"e_1_2_1_38_1","first-page":"41","article-title":"Lower bounds based on the exponential time hypothesis","volume":"105","author":"Lokshtanov Daniel","year":"2011","unstructured":"Daniel Lokshtanov , D\u00e1niel Marx , and Saket Saurabh . 2011 . Lower bounds based on the exponential time hypothesis . Bull. EATCS 105 (2011), 41 -- 72 . Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41--72.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_39_1","volume-title":"Lower bounds based on the exponential time hypothesis. Bull. EATCS 3, 105","author":"Lokshtanov Daniel","year":"2013","unstructured":"Daniel Lokshtanov , D\u00e1niel Marx , and Saket Saurabh . 2013. Lower bounds based on the exponential time hypothesis. Bull. EATCS 3, 105 ( 2013 ). Daniel Lokshtanov, D\u00e1niel Marx, and Saket Saurabh. 2013. Lower bounds based on the exponential time hypothesis. Bull. EATCS 3, 105 (2013)."},{"volume-title":"Large Networks and Graph Limits","author":"Lov\u00e1sz L\u00e1szl\u00f3","key":"e_1_2_1_40_1","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 2012. Large Networks and Graph Limits . Vol. 60 . American Mathematical Soc . L\u00e1szl\u00f3 Lov\u00e1sz. 2012. Large Networks and Graph Limits. Vol. 60. American Mathematical Soc."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2010.v006a005"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914)","author":"Marx D\u00e1niel","year":"2014","unstructured":"D\u00e1niel Marx and Michal Pilipczuk . 2014 . Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask) . In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914) . 542--553. D\u00e1niel Marx and Michal Pilipczuk. 2014. Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask). In Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS\u201914). 542--553."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90032-5"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.02.012"},{"key":"e_1_2_1_47_1","unstructured":"Michael Sipser. 2005. Introduction to the Theory of Computation. Cengage Learning. Michael Sipser. 2005. Introduction to the Theory of Computation. Cengage Learning."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206038"},{"volume-title":"Parameterized and Exact Computation","author":"Traxler Patrick","key":"e_1_2_1_49_1","unstructured":"Patrick Traxler . 2008. The time complexity of constraint satisfaction . In Parameterized and Exact Computation . Springer , 190--201. Patrick Traxler. 2008. The time complexity of constraint satisfaction. In Parameterized and Exact Computation. Springer, 190--201."},{"key":"e_1_2_1_50_1","unstructured":"Magnus Wahlstr\u00f6m. 2010. Problem 5.21. time complexity of graph homomorphism. In Exact Complexity of NP-Hard Problems. Dagstuhl Seminar 10441 Final Report Ramamohan Paturi Thore Husfeldt Dieter Kratsch and Gregory Sorkin (Eds.). Dagstuhl. Magnus Wahlstr\u00f6m. 2010. Problem 5.21. time complexity of graph homomorphism. In Exact Complexity of NP-Hard Problems. Dagstuhl Seminar 10441 Final Report Ramamohan Paturi Thore Husfeldt Dieter Kratsch and Gregory Sorkin (Eds.). Dagstuhl."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9261-z"},{"volume-title":"Combinatorial Optimization\u2014Eureka, You Shrink!Lecture Notes in Computer Science","author":"Woeginger Gerhard J.","key":"e_1_2_1_52_1","unstructured":"Gerhard J. Woeginger . 2003. Exact algorithms for NP-hard problems: A survey . In Combinatorial Optimization\u2014Eureka, You Shrink!Lecture Notes in Computer Science , Vol. 2570 . Springer-Verlag , Berlin , 185--207. Gerhard J. Woeginger. 2003. Exact algorithms for NP-hard problems: A survey. In Combinatorial Optimization\u2014Eureka, You Shrink!Lecture Notes in Computer Science, Vol. 2570. Springer-Verlag, Berlin, 185--207."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3051094","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3051094","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,31]],"date-time":"2022-12-31T08:47:52Z","timestamp":1672476472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3051094"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,16]]},"references-count":52,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,6,30]]}},"alternative-id":["10.1145\/3051094"],"URL":"https:\/\/doi.org\/10.1145\/3051094","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2017,6,16]]},"assertion":[{"value":"2016-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}