文章基本信息

标题：Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
本地全文：下载
作者：Fedor V. Fomin ; Daniel Lokshtanov ; Ivan Mihajlin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：49:1-49:18
DOI：10.4230/LIPIcs.ICALP.2020.49
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We prove that the Hadwiger number of an n-vertex graph G (the maximum size of a clique minor in G) cannot be computed in time n^o(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^o(n)-time algorithms (up to ETH) for a large class of computational problems concerning edge contractions in graphs.
关键词：Hadwiger Number; Exponential-Time Hypothesis; Exact Algorithms; Edge Contraction Problems