Back to Search Start Over

Inapproximability of Diameter in super-linear time: Beyond the 5/3 ratio

Authors :
Bonnet, Édouard
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