论文标题
Hadwiger编号和相关收缩问题的计算：紧密的下限
Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
论文作者
论文摘要
我们证明，除非指数时间假设（ETH）失败，否则无法计算出$ n $ vertex图$ g $的hadwiger数量（$ g $中的最大大小）。这在确切的指数算法领域解决了一个众所周知的开放问题。解决Hadwiger数字问题开发的技术具有更大的适用性。我们使用它来排除$ n^{o（n）} $ - 时间算法（最多ETH）的存在，以了解有关图形中边缘收缩的大量计算问题。
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.
