License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2020.49
URN: urn:nbn:de:0030-drops-124568
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12456/
Go to the corresponding LIPIcs Volume Portal

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

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

pdf-format:
LIPIcs-ICALP-2020-49.pdf (3 MB)

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.

BibTeX - Entry

@InProceedings{fomin_et_al:LIPIcs:2020:12456,
  author =	{Fedor V. Fomin and Daniel Lokshtanov and Ivan Mihajlin and Saket Saurabh and Meirav Zehavi},
  title =	{{Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{49:1--49:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Artur Czumaj and Anuj Dawar and Emanuela Merelli},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12456},
  URN =		{urn:nbn:de:0030-drops-124568},
  doi =		{10.4230/LIPIcs.ICALP.2020.49},
  annote =	{Keywords: Hadwiger Number, Exponential-Time Hypothesis, Exact Algorithms, Edge Contraction Problems}
}

Keywords: Hadwiger Number, Exponential-Time Hypothesis, Exact Algorithms, Edge Contraction Problems
Collection: 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Issue Date: 2020
Date of publication: 29.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI