A note on hardness of diameter approximation

DOI10.1016/J.IPL.2017.12.010MaRDI QIDQ1705693zbMATH OpenOpenAlexFDO

Authors Karl Bringmann, Sebastian Krinninger

Publication date 16 March 2018

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

distributed computinglower boundsgraph algorithmshardness in P

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Abstract: We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, $ildeOmega(n)$ rounds are necessary to compute the diameter [Frischknecht et al. SODA'12], where $ildeOmega(cdot)$ hides polylogarithmic factors. Abboud et al. [DISC 2016] extended this result to sparse graphs and, at a more fine-grained level, showed that, for any integer $1leqellleqoperatornamepolylog(n)$, distinguishing between networks of diameter $4ell+2$ and $6ell+1$ requires $ildeOmega(n)$ rounds. We slightly tighten this result by showing that even distinguishing between diameter $2ell+1$ and $3ell+1$ requires $ildeOmega(n)$ rounds. The reduction of Abboud et al. is inspired by recent conditional lower bounds in the RAM model, where the orthogonal vectors problem plays a pivotal role. In our new lower bound, we make the connection to orthogonal vectors explicit, leading to a conceptually more streamlined exposition.

Recommendations

• Networks cannot compute their diameter in sublinear time
• Distributed algorithms for network diameter and girth
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Toward Tight Approximation Bounds for Graph Diameter and Eccentricities

Cites work

• A new algorithm for optimal 2-constraint satisfaction and its implications
• Better approximation algorithms for the graph diameter
• Communication Complexity
• Distributed Computing: A Locality-Sensitive Approach
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Networks cannot compute their diameter in sublinear time
• New bounds for approximating extremal distances in undirected graphs
• On the distributional complexity of disjointness
• Which problems have strongly exponential complexity?

Cited in

(7)

• Networks cannot compute their diameter in sublinear time
• Distributed algorithms for network diameter and girth
• Sublinear-time quantum computation of the diameter in CONGEST networks
• The cost of unknown diameter in dynamic networks
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-hard at Time n ^4/3
• Improved hardness of approximation of diameter in the CONGEST model

This page was built for publication: A note on hardness of diameter approximation

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