{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:46Z","timestamp":1750220446716,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel - United States Binational Science Foundation","award":["819416"],"award-info":[{"award-number":["819416"]}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2008838"],"award-info":[{"award-number":["2008838"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["MULTIVAL"],"award-info":[{"award-number":["MULTIVAL"]}],"id":[{"id":"10.13039\/501100005416","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            We prove that the Hadwiger number of an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            (the maximum size of a clique minor in\n            <jats:italic>G<\/jats:italic>\n            ) cannot be computed in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            , unless the Exponential Time Hypothesis (ETH) fails. This resolves a well-known open question in the area of exact exponential algorithms. The technique developed for resolving the Hadwiger number problem has a wider applicability. We use it to rule out the existence of\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>o<\/jats:italic>\n              (\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            -time algorithms (up to the ETH) for a large class of computational problems concerning edge contractions in graphs.\n          <\/jats:p>","DOI":"10.1145\/3448639","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T16:31:02Z","timestamp":1616776262000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Computation of Hadwiger Number and Related Contraction Problems"],"prefix":"10.1145","volume":"13","author":[{"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[{"name":"University of California, San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute for Mathematical Sciences, HBNI, India and University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1259638"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS","author":"Agrawal Akanksha","year":"2017","unstructured":"Akanksha Agrawal , Daniel Lokshtanov , Saket Saurabh , and Meirav Zehavi . 2017 . Split contraction: The untold story . In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2017. Split contraction: The untold story. In Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80001-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2005.05.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3051094"},{"key":"e_1_2_1_8_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer-Verlag , New York. Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer-Verlag, New York."},{"key":"e_1_2_1_9_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010","unstructured":"Fedor V. Fomin and Dieter Kratsch . 2010 . Exact Exponential Algorithms. Springer . An EATCS Series: Texts in Theoretical Computer Science. Fedor V. Fomin and Dieter Kratsch. 2010. Exact Exponential Algorithms. Springer. An EATCS Series: Texts in Theoretical Computer Science."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) (Virtual Conference). 49:1\u201349:18","author":"Fomin Fedor V.","year":"2020","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Ivan Mihajlin , Saket Saurabh , and Meirav Zehavi . 2020 . Computation of Hadwiger number and related contraction problems: Tight lower bounds . In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) (Virtual Conference). 49:1\u201349:18 . Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. 2020. Computation of Hadwiger number and related contraction problems: Tight lower bounds. In Proceedings of the 47th International Colloquium on Automata, Languages, and Programming (ICALP\u201920) (Virtual Conference). 49:1\u201349:18."},{"volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","key":"e_1_2_1_11_1","unstructured":"Martin Charles Golumbic . 2004. Algorithmic Graph Theory and Perfect Graphs . North-Holland Publishing Co., Amsterdam , The Netherlands . Martin Charles Golumbic. 2004. Algorithmic Graph Theory and Perfect Graphs. North-Holland Publishing Co., Amsterdam, The Netherlands."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993700"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1999.766282"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90065-X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.10.003"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"volume-title":"Parameterized and Exact Computation","author":"Traxler Patrick","key":"e_1_2_1_18_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."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448639","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448639","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448639","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:43Z","timestamp":1750193263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448639"}},"subtitle":["Tight Lower Bounds"],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3448639"],"URL":"https:\/\/doi.org\/10.1145\/3448639","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}