Computation of Hadwiger number and related contraction problems. Tight lower bounds

DOI10.1145/3448639MaRDI QIDQ5065632zbMATH OpenOpenAlexWikidataFDO

Authors Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, Meirav Zehavi

Publication date 22 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2004.11621

zbMATH Keywords

exact algorithmsHadwiger numberexponential-time hypothesisedge contraction problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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.

Recommendations

• On the complexity of approximating the Hadwiger number
• Lower bound of the Hadwiger number of graphs by their average degree
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction

Cited in

(1)

• On the complexity of approximating the Hadwiger number

This page was built for publication: Computation of Hadwiger number and related contraction problems. Tight lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5065632)