First local-computation-algorithm treatment of low-out-degree edge orientation, with a Ω(√n/r) lower bound on forests and sublinear r-orientation and 4-coloring algorithms for bounded-degree forests.
Non-Local Probes Do Not Help with Graph Problems
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Locally computing edge orientations
First local-computation-algorithm treatment of low-out-degree edge orientation, with a Ω(√n/r) lower bound on forests and sublinear r-orientation and 4-coloring algorithms for bounded-degree forests.