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

2020/04/24 by Fomin, Fedor V., Lokshtanov, Daniel, Mihajlin, Ivan +2 · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2004.11621

Abstract

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.

Cited by

• A Finer View of the Parameterized Landscape of Labeled Graph Contractions

Related

• Hadwiger number of graphs with small chordality
• On Hadwiger Conjecture
• On Hadwiger's Number of a graph with partial information
• Hadwiger's conjecture: finite vs infinite graphs
• Reducing the Vertex Cover Number via Edge Contractions