4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n 4/3

DOI10.1145/3494540MaRDI QIDQ6058239zbMATH OpenOpenAlexFDO

Authors Édouard Bonnet

Publication date 31 October 2023

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

diameterinapproximabilityk-orthogonal vectorsSETH lower bounds

Mathematics Subject Classification ID

Computer science (68-XX)

Abstract: We show, assuming the Strong Exponential Time Hypothesis, that for every $varepsilon>0$, approximating undirected unweighted Diameter on $n$-vertex $n^{1+o(1)}$-edge graphs within ratio $7/4-varepsilon$ requires $m^{4/3-o(1)}$ time. This is the first result that conditionally rules out a near-linear time $5/3$-approximation for undirected Diameter.

Recommendations

• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities
• Towards tight approximation bounds for graph diameter and eccentricities
• Better approximation algorithms for the graph diameter
• Fast approximation algorithms for the diameter and radius of sparse graphs
• A note on hardness of diameter approximation

Cited in

(1)

• Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs

This page was built for publication: 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n ^4/3

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