Will Rosenbaum · Jukka Suomela

Seeing far vs. seeing wide: volume complexity of local graph problems

PODC 2020 · 39th ACM Symposium on Principles of Distributed Computing, Salerno, Italy, August 2020

authors’ version arXiv.org


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:

  • If the deterministic distance is linear, it is also known that randomized distance is near-linear. We show that volume complexity is fundamentally different: there are problems with a linear deterministic volume but only logarithmic randomized volume.
  • We prove a volume hierarchy theorem for randomized complexity: Among problems with (near) linear deterministic volume complexity, there are infinitely many distinct randomized volume complexity classes between $\Omega(\log n)$ and $O(n)$. Moreover, this hierarchy persists even when restricting to problems whose randomized and deterministic distance complexities are $\Theta(\log n)$.
  • Similar hierarchies exist for polynomial distance complexities: we show that for any $k, \ell \in \mathbb{N}$ with $k \leq \ell$, there are problems whose randomized and deterministic distance complexities are $\Theta(n^{1/\ell})$, randomized volume complexities are $\tilde\Theta(n^{1/k})$, and whose deterministic volume complexities are $\tilde\Theta(n)$.

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.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.