LIPIcs.ICALP.2021.34.pdf
- Filesize: 0.83 MB
- 15 pages
Document
4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time n^{4/3}
Author
Édouard Bonnet 
-
Part of:
Volume:
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-07-02
File
Document Identifiers
Author Details
Cite As Get BibTex
Édouard Bonnet. 4 vs 7 Sparse Undirected Unweighted Diameter is SETH-Hard at Time n^{4/3}. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.34
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 m^{4/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.
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. Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio. CoRR, To appear at STACS 2021, abs/2008.11315, 2020. URL: http://arxiv.org/abs/2008.11315.
- 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.
- Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On Problems as Hard as CNF-SAT. ACM Trans. Algorithms, 12(3):41:1-41:24, 2016. URL: https://doi.org/10.1145/2925416.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
- 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 and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: https://doi.org/10.1006/jcss.2000.1727.
- 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.
- Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the Exponential Time Hypothesis. Bull. EATCS, 105:41-72, 2011. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/92.
- 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.
