PODC 2020 · 39th ACM Symposium on Principles of Distributed Computing, Salerno, Italy, August 2020
Assume we have a graph problem that is locally checkable but not locally solvable—given a solution we can check that it is feasible by verifying all constant-radius neighborhoods, but to find a feasible solution each node needs to explore the input graph at least up to distance $\Omega(\log n)$ in order to produce its own part of the solution.
Such problems have been studied extensively in the recent years in the area of distributed computing, where the key complexity measure has been distance: how far does a node need to see in order to produce its own part of the solution. However, if we are interested in e.g. sublinear-time centralized algorithms, a much more appropriate complexity measure would be volume: how large a subgraph does a node need to see in order to produce its own part of the solution.
In this work we study locally checkable graph problems on bounded-degree graphs and we give a number of constructions that exhibit different tradeoffs between deterministic distance, randomized distance, deterministic volume, and randomized volume:
Additionally, we consider connections between our volume model and massively parallel computation (MPC). We give a general simulation argument that any volume-efficient algorithm can be transformed into a space-efficient MPC algorithm.