Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)

DOI10.1145/3406325.3451045arXiv2008.05106OpenAlexW3171978723MaRDI QIDQ6065285

Ray Li

Publication date: 14 November 2023

Published in: (Search for Journal in Brave)

Abstract: We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any $varepsilon>0$, assuming the Strong Exponential Time Hypothesis (SETH), there are no near-linear time $2-varepsilon$-approximation algorithms for the Diameter of a sparse directed graph, even in unweighted graphs. This result shows that a simple near-linear time 2-approximation algorithm for Diameter is optimal under SETH, answering a question from a survey of Rubinstein and Vassilevska-Williams (SIGACT '19) for the case of directed graphs. In the same survey, Rubinstein and Vassilevska-Williams also asked if it is possible to show that there are no $2-varepsilon$ approximation algorithms for Diameter in a directed graph in $O(n^{1.499})$ time. We show that, assuming a hypothesis called NSETH, one cannot use a deterministic SETH-based reduction to rule out the existence of such algorithms. Extending the techniques in these two results, we characterize whether a $2-varepsilon$ approximation algorithm running in time $O(n^{1+delta})$ for the Diameter of a sparse directed unweighted graph can be ruled out by a deterministic SETH-based reduction for every $deltain(0,1)$ and essentially every $varepsilonin(0,1)$, assuming NSETH. This settles the SETH-hardness of approximating the diameter of sparse directed unweighted graphs for deterministic reductions, up to NSETH. We make the same characterization for randomized SETH-based reductions, assuming another hypothesis called NUNSETH. We prove additional hardness and non-reducibility results for undirected graphs.

Full work available at URL: https://arxiv.org/abs/2008.05106

zbMATH Keywords

graph diameterstrong exponential time hypothesisfine-grained complexitynon-deterministic algorithmhopset

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

Removing additive structure in 3SUM-based reductions

This page was built for publication: Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6065285)