التفاصيل البيبلوغرافية
| العنوان: |
Hardness of Approximate Diameter: Now for Undirected Graphs. |
| المؤلفون: |
Dalirrooyfard, Mina, Li, Ray, Vassilevska Williams, Virginia |
| المصدر: |
Journal of the ACM; Feb2025, Vol. 72 Issue 1, p1-32, 32p |
| مصطلحات موضوعية: |
UNDIRECTED graphs, HARDNESS, INTEGERS, DIAMETER, GENERALIZATION, DIRECTED 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 time. A series of articles 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-\frac{1}{k}-\delta\) approximation for diameter in directed m-edge graphs requires \(m^{1+1/(k-1)-o(1)}\) time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this article, we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC'13], [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 conditionally 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. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |