2026-08-08T00:00:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13662 2024-03-06T10:52:36Z ddc:004 open_access

Inapproximability of Diameter in Super-Linear Time: Beyond the 5/3 Ratio Bonnet, Édouard Diameter inapproximability SETH lower bounds k-Orthogonal Vectors We show, assuming the Strong Exponential Time Hypothesis, that for every ε > 0, approximating directed Diameter on m-arc graphs within ratio 7/4 - ε requires m^{4/3 - o(1)} time. Our construction uses non-negative 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 = O˜(n). This is the first result that conditionally rules out a near-linear time 5/3-approximation for a variant of Diameter. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet 2021 Is Part Of LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2021.17 urn:nbn:de:0030-drops-136623 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.17 eng https://creativecommons.org/licenses/by/4.0/legalcode