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

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



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.49.pdf
  • Filesize: 3.25 MB
  • 18 pages

Document Identifiers

Author Details

Fedor V. Fomin
  • University of Bergen, Norway
Daniel Lokshtanov
  • University of California, Santa Barbara, CA, USA
Ivan Mihajlin
  • University of California, San Diego, CA, USA
Saket Saurabh
  • Department of Informatics, University of Bergen, Norway
  • The Institute of Mathematical Sciences, Chennai, India
Meirav Zehavi
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel

Cite AsGet BibTex

Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ICALP.2020.49

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Hadwiger Number
  • Exponential-Time Hypothesis
  • Exact Algorithms
  • Edge Contraction Problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Akanksha Agrawal, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Split contraction: The untold story. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  2. Andreas Björklund. Determinant sums for undirected hamiltonicity. SIAM J. Comput., 43(1):280-299, 2014. URL: https://doi.org/10.1137/110839229.
  3. Andreas Björklund, Thore Husfeldt, and Mikko Koivisto. Set partitioning via inclusion-exclusion. SIAM J. Computing, 39(2):546-563, 2009. Google Scholar
  4. B. Bollobás, P. A. Catlin, and P. Erdős. Hadwiger’s conjecture is true for almost every graph. European J. Combin., 1(3):195-199, 1980. URL: https://doi.org/10.1016/S0195-6698(80)80001-1.
  5. Jianer Chen, Benny Chor, Michael R. Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, and Ge Xia. Tight lower bounds for certain parameterized NP-hard problems. Information and Computation, 201(2):216-231, 2005. URL: https://doi.org/10.1016/j.ic.2005.05.001.
  6. Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, and Arkadiusz Socala. Tight lower bounds on graph embedding problems. J. ACM, 64(3):18:1-18:22, 2017. URL: https://doi.org/10.1145/3051094.
  7. Rodney G. Downey and Michael R. Fellows. Parameterized complexity. Springer-Verlag, New York, 1999. Google Scholar
  8. Fedor V. Fomin and Dieter Kratsch. Exact Exponential Algorithms. Springer, 2010. An EATCS Series: Texts in Theoretical Computer Science. Google Scholar
  9. Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of hadwiger number and related contraction problems: Tight lower bounds. CoRR, abs/2004.11621, 2020. URL: http://arxiv.org/abs/2004.11621.
  10. Martin Charles Golumbic. Algorithmic Graph Theory and Perfect Graphs. North-Holland Publishing Co., Amsterdam, The Netherlands, The Netherlands, 2004. Google Scholar
  11. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, and Paul Wollan. Finding topological subgraphs is fixed-parameter tractable. In Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, pages 479-488, 2011. Google Scholar
  12. Eugene L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5(3):66-67, 1976. Google Scholar
  13. Andrzej Lingas and Martin Wahlen. An exact algorithm for subgraph homeomorphism. J. Discrete Algorithms, 7(4):464-468, 2009. URL: https://doi.org/10.1016/j.jda.2008.10.003.
  14. Neil Robertson and Paul D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Combinatorial Theory Ser. B, 63(1):65-110, 1995. Google Scholar
  15. Patrick Traxler. The time complexity of constraint satisfaction. In Parameterized and Exact Computation, pages 190-201. Springer, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail