{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,4]],"date-time":"2022-06-04T10:41:35Z","timestamp":1654339295245},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T00:00:00Z","timestamp":1648252800000},"content-version":"vor","delay-in-days":269,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel - United States Binational Science Foundation","award":["819416"]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2008838"]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["819416"]},{"DOI":"10.13039\/501100005416","name":"Research Council of Norway","doi-asserted-by":"crossref","award":["MULTIVAL"]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1176\/18"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"\n We prove that the Hadwiger number of an\n n<\/jats:italic>\n -vertex graph\n G<\/jats:italic>\n (the maximum size of a clique minor in\n G<\/jats:italic>\n ) cannot be computed in time\n n<\/jats:italic>\n \n o<\/jats:italic>\n (\n 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 n<\/jats:italic>\n \n o<\/jats:italic>\n (\n 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","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"}]},{"given":"Daniel","family":"Lokshtanov","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, USA"}]},{"given":"Ivan","family":"Mihajlin","sequence":"additional","affiliation":[{"name":"University of California, San Diego, USA"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute for Mathematical Sciences, HBNI, India and University of Bergen, Norway"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Israel"}]}],"member":"320","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.5555\/1103348.1709478"},{"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."},{"key":"e_1_2_1_11_1","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic Martin Charles","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"},{"key":"e_1_2_1_18_1","volume-title":"Parameterized and Exact Computation","author":"Traxler Patrick","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\/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":[[2022,6,4]],"date-time":"2022-06-04T10:06:47Z","timestamp":1654337207000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448639"}},"subtitle":["Tight Lower Bounds"],"short-title":[],"issued":{"date-parts":[[2021,6,30]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3448639"],"URL":"http:\/\/dx.doi.org\/10.1145\/3448639","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":["Computational Theory and Mathematics","Theoretical Computer Science"],"published":{"date-parts":[[2021,6,30]]}}}