LIPIcs.STACS.2021.17.pdf
- Filesize: 0.73 MB
- 13 pages
Document
Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio
Author
Édouard Bonnet 
-
Part of:
Volume:
38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-03-10
File
Document Identifiers
Author Details
Cite As Get BibTex
Édouard Bonnet. Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.STACS.2021.17
Abstract
We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating directed Diameter on m-arc graphs within ratio 7/4 - ε requires m^{4/3 - o(1)} time. Our construction uses non-negative edge weights but even holds for sparse digraphs, i.e., for which the number of vertices n and the number of arcs m satisfy m = O˜(n). This is the first result that conditionally rules out a near-linear time 5/3-approximation for a variant of Diameter.
Subject Classification
ACM Subject Classification
- Theory of computation → Graph algorithms analysis
Keywords
- Diameter
- inapproximability
- SETH lower bounds
- k-Orthogonal Vectors
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication). SIAM J. Comput., 28(4):1167-1181, 1999. URL: https://doi.org/10.1137/S0097539796303421.
- Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein. Towards tight approximation bounds for graph diameter and eccentricities. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 267-280. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188950.
- Édouard Bonnet. 4 vs 7 sparse undirected unweighted Diameter is SETH-hard at time n^4/3, 2021. URL: http://arxiv.org/abs/2101.02312.
- Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New Bounds for Approximating Extremal Distances in Undirected Graphs. In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 363-376. SIAM, 2016. URL: https://doi.org/10.1137/1.9781611974331.ch27.
- Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Madhu Sudan, editor, Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 261-270. ACM, 2016. URL: https://doi.org/10.1145/2840728.2840746.
- Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. Better Approximation Algorithms for the Graph Diameter. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 1041-1052. SIAM, 2014. URL: https://doi.org/10.1137/1.9781611973402.78.
- Mina Dalirrooyfard and Nicole Wein. Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs. CoRR, abs/2011.03892, 2020. URL: http://arxiv.org/abs/2011.03892.
- Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: https://doi.org/10.1006/jcss.2001.1774.
- Ray Li. Improved SETH-hardness of unweighted Diameter. CoRR, abs/2008.05106, 2020. URL: http://arxiv.org/abs/2008.05106.
- Ray Li. Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH). CoRR, abs/2008.05106, 2020. URL: http://arxiv.org/abs/2008.05106.
- Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 515-524. ACM, 2013. URL: https://doi.org/10.1145/2488608.2488673.
- Aviad Rubinstein and Virginia Vassilevska Williams. SETH vs Approximation. SIGACT News, 50(4):57-76, 2019. URL: https://doi.org/10.1145/3374857.3374870.
- Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci., 348(2-3):357-365, 2005. URL: https://doi.org/10.1016/j.tcs.2005.09.023.
-
Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the ICM, volume 3, pages 3431-3472. World Scientific, 2018.
