A note on hardness of diameter approximation

DOI10.1016/J.IPL.2017.12.010zbMATH Open1427.68106arXiv1705.02127OpenAlexW2613923799MaRDI QIDQ1705693FDOQ1705693

Authors: Karl Bringmann, Sebastian Krinninger 

Publication date: 16 March 2018

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

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.

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

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

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)

Cites Work

• Which problems have strongly exponential complexity?
• Distributed Computing: A Locality-Sensitive Approach
• Fast approximation algorithms for the diameter and radius of sparse graphs
• Title not available (Why is that?)
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Communication Complexity
• On the distributional complexity of disjointness
• New Bounds for Approximating Extremal Distances in Undirected Graphs
• Better Approximation Algorithms for the Graph Diameter
• Near-linear lower bounds for distributed distance computations, even in sparse networks

Cited In (2)

• Distributed algorithms for network diameter and girth
• 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)