Back to Search
Start Over
Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio
- Publication Year :
- 2020
-
Abstract
- We show, assuming the Strong Exponential Time Hypothesis, that for every $\varepsilon > 0$, approximating directed Diameter on $m$-arc graphs within ratio $7/4 - \varepsilon$ requires $m^{4/3 - o(1)}$ time. Our construction uses nonnegative 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 = n \log^{O(1)} n$. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for Diameter.<br />Comment: 13 pages, 4 figures, expanded introduction and discussion on follow-up works
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2008.11315
- Document Type :
- Working Paper