Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds

Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin +2

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 Hypothes…