Non-local probes do not help with many graph problems

DOI10.1007/978-3-662-53426-7_15MaRDI QIDQ1660935zbMATH OpenOpenAlexFDO

Authors Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela

Publication date 16 August 2018

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Abstract: This work bridges the gap between distributed and centralised models of computing in the context of sublinear-time graph algorithms. A priori, typical centralised models of computing (e.g., parallel decision trees or centralised local algorithms) seem to be much more powerful than distributed message-passing algorithms: centralised algorithms can directly probe any part of the input, while in distributed algorithms nodes can only communicate with their immediate neighbours. We show that for a large class of graph problems, this extra freedom does not help centralised algorithms at all: for example, efficient stateless deterministic centralised local algorithms can be simulated with efficient distributed message-passing algorithms. In particular, this enables us to transfer existing lower bound results from distributed algorithms to centralised local algorithms.

Recommendations

• scientific article; zbMATH DE number 7075933
• Best of two local models: centralized local and distributed local algorithms
• Deterministic stateless centralized local algorithms for bounded degree graphs
• On the probe complexity of local computation algorithms
• On the complexity of local distributed graph problems

Cited in

(5)

• On the probe complexity of local computation algorithms
• ``Global graph problems tend to be intractable
• Best of two local models: centralized local and distributed local algorithms
• Can we locally compute sparse connected subgraphs?
• Constant-time local computation algorithms

This page was built for publication: Non-local probes do not help with many graph problems

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