Hardness of Approximate Diameter: Now for Undirected Graphs
Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear tim...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
ACM
2024
|
| Online Access: | https://hdl.handle.net/1721.1/157750 |
| _version_ | 1824458089281093632 |
|---|---|
| author | Dalirrooyfard, Mina Li, Ray Vassilevska Williams, Virginia |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Dalirrooyfard, Mina Li, Ray Vassilevska Williams, Virginia |
| author_sort | Dalirrooyfard, Mina |
| collection | MIT |
| description | Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer k?2 and ?>0, a (2-(1/k)-?) approximation for diameter in directed m-edge graphs requires mn1+1/(k-1)-o(1) time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC', [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve, k=2,3 and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is also optimal for undirected graphs. To obtain our result, we extract the core ideas in known reductions and introduce a unification and generalization that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation. |
| first_indexed | 2025-02-19T04:20:21Z |
| format | Article |
| id | mit-1721.1/157750 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2025-02-19T04:20:21Z |
| publishDate | 2024 |
| publisher | ACM |
| record_format | dspace |
| spelling | mit-1721.1/1577502025-01-04T05:58:32Z Hardness of Approximate Diameter: Now for Undirected Graphs Dalirrooyfard, Mina Li, Ray Vassilevska Williams, Virginia Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer k?2 and ?>0, a (2-(1/k)-?) approximation for diameter in directed m-edge graphs requires mn1+1/(k-1)-o(1) time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC', [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve, k=2,3 and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is also optimal for undirected graphs. To obtain our result, we extract the core ideas in known reductions and introduce a unification and generalization that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation. 2024-12-04T19:19:08Z 2024-12-04T19:19:08Z 2024-12-01T08:45:16Z Article http://purl.org/eprint/type/JournalArticle 0004-5411 https://hdl.handle.net/1721.1/157750 Dalirrooyfard, Mina, Li, Ray and Vassilevska Williams, Virginia. "Hardness of Approximate Diameter: Now for Undirected Graphs." Journal of the ACM. PUBLISHER_POLICY en http://dx.doi.org/10.1145/3704631 Journal of the ACM Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. The author(s) application/pdf ACM Association for Computing Machinery |
| spellingShingle | Dalirrooyfard, Mina Li, Ray Vassilevska Williams, Virginia Hardness of Approximate Diameter: Now for Undirected Graphs |
| title | Hardness of Approximate Diameter: Now for Undirected Graphs |
| title_full | Hardness of Approximate Diameter: Now for Undirected Graphs |
| title_fullStr | Hardness of Approximate Diameter: Now for Undirected Graphs |
| title_full_unstemmed | Hardness of Approximate Diameter: Now for Undirected Graphs |
| title_short | Hardness of Approximate Diameter: Now for Undirected Graphs |
| title_sort | hardness of approximate diameter now for undirected graphs |
| url | https://hdl.handle.net/1721.1/157750 |
| work_keys_str_mv | AT dalirrooyfardmina hardnessofapproximatediameternowforundirectedgraphs AT liray hardnessofapproximatediameternowforundirectedgraphs AT vassilevskawilliamsvirginia hardnessofapproximatediameternowforundirectedgraphs |