Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n4/3

Published: 04 March 2022 Publication History

Abstract

We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating undirected unweighted Diameter on n-vertex m-edge graphs within ratio 7/4 - ε requires m4/3 - o(1) time, even when m = Õ(n). This is the first result that conditionally rules out a near-linear time 5/3-approximation for undirected Diameter.

References

[1]
Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. 1999. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28, 4 (1999), 1167–1181. DOI:
[2]
Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. 2018. Towards tight approximation bounds for graph diameter and eccentricities. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC’18), Ilias Diakonikolas, David Kempe, and Monika Henzinger (Eds.). ACM, 267–280. DOI:
[3]
Édouard Bonnet. 2021. Inapproximability of diameter in super-linear time: Beyond the 5/3 ratio. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS’21), Markus Bläser and Benjamin Monmege (Eds.), LIPIcs, Vol. 187. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 17:1–17:13. DOI:
[4]
Massimo Cairo, Roberto Grossi, and Romeo Rizzi. 2016. New bounds for approximating extremal distances in undirected graphs. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’16), Robert Krauthgamer (Ed.). SIAM, 363–376. DOI:
[5]
Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. 2016. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the ACM Conference on Innovations in Theoretical Computer Science, Madhu Sudan (Ed.). ACM, 261–270. DOI:
[6]
Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. 2014. Better approximation algorithms for the graph diameter. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14), Chandra Chekuri (Ed.). SIAM, 1041–1052. DOI:
[7]
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. 2016. On problems as hard as CNF-SAT. ACM Trans. Algor. 12, 3 (2016), 41:1–41:24. DOI:
[8]
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer. DOI:
[9]
Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. 2021. Hardness of approximate diameter: Now for undirected graphs. arXiv:2106.06026. Retrieved from https://arxiv.org/abs/2106.06026.
[10]
Mina Dalirrooyfard and Nicole Wein. 2021. Tight conditional lower bounds for approximating diameter in directed graphs. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC’21), Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 1697–1710. DOI:
[11]
Russell Impagliazzo and Ramamohan Paturi. 2001. On the complexity of k-SAT. J. Comput. Syst. Sci. 62, 2 (2001), 367–375. DOI:
[12]
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. 2001. Which problems have strongly exponential complexity?J. Comput. Syst. Sci. 63, 4 (2001), 512–530. DOI:
[13]
Ray Li. 2020. Improved SETH-hardness of unweighted diameter. arXiv2008.05106. Retrieved from https://arxiv.org/abs/2008.05106.
[14]
Ray Li. 2021. Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH). In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, Samir Khuller and Virginia Vassilevska Williams (Eds.). ACM, 1684–1696. DOI:
[15]
Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. 2011. Lower bounds based on the exponential time hypothesis. Bull. EATCS 105 (2011), 41–72.
[16]
Liam Roditty and Virginia Vassilevska Williams. 2013. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proceedings of the Symposium on Theory of Computing Conference (STOC’13), Dan Boneh, Tim Roughgarden, and Joan Feigenbaum (Eds.). ACM, 515–524. DOI:
[17]
Aviad Rubinstein and Virginia Vassilevska Williams. 2019. SETH vs approximation. SIGACT News 50, 4 (2019), 57–76. DOI:
[18]
Ryan Williams. 2005. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. 348, 2–3 (2005), 357–365. DOI:
[19]
Virginia Vassilevska Williams. 2018. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Conference on Microelectronics (ICM’18), Vol. 3. World Scientific, Singapore, 3431–3472.

Cited By

View all
  • (2022)Hardness of Approximate Diameter: Now for Undirected Graphs2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00102(1021-1032)Online publication date: Feb-2022

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms
ACM Transactions on Algorithms  Volume 18, Issue 2
April 2022
285 pages
ISSN:1549-6325
EISSN:1549-6333
DOI:10.1145/3514175
  • Editor:
  • Edith Cohen
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 March 2022
Accepted: 01 October 2021
Revised: 01 October 2021
Received: 01 May 2021
Published in TALG Volume 18, Issue 2

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Diameter
  2. inapproximability
  3. SETH lower bounds
  4. k-Orthogonal Vectors

Qualifiers

  • Research-article
  • Refereed

Funding Sources

  • ANR project DIGRAPHS

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)21
  • Downloads (Last 6 weeks)2
Reflects downloads up to 14 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2022)Hardness of Approximate Diameter: Now for Undirected Graphs2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00102(1021-1032)Online publication date: Feb-2022

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Full Text

View this article in Full Text.

Full Text

HTML Format

View this article in HTML Format.

HTML Format

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media