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

DOI10.1145/3448639zbMATH Open1495.68169arXiv2004.11621OpenAlexW3144509434WikidataQ130966978 ScholiaQ130966978MaRDI QIDQ5065632FDOQ5065632

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)

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.

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

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

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)

Cited In (2)

• Hadwiger number of graphs with small chordality
• 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)