# Fast Distributed Algorithms for Testing Graph Properties

arXiv: https://arxiv.org/abs/1602.03718 · HTML: https://mlsanity.com/paper/1602.03718/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2016.

## Built on by (most cited first, 1 of 1)

- [Collaborative Learning in General Graphs with Limited Memorization: Complexity, Learnability, and Reliability](https://mlsanity.com/paper/2201.12482/) (2022)

## Abstract (arXiv)

We initiate a thorough study of distributed property testing -- producing algorithms for the approximation problems of property testing in the CONGEST model. In particular, for the so-called dense testing model we emulate sequential tests for nearly all graph properties having 1-sided tests, while in the sparse and general models we obtain faster tests for triangle-freeness and bipartiteness respectively. In most cases, aided by parallelism, the distributed algorithms have a much shorter running time as compared to their counterparts from the sequential querying model of traditional property testing. The simplest property testing algorithms allow a relatively smooth transitioning to the distributed model. For the more complex tasks we develop new machinery that is of independent interest. This includes a method for distributed maintenance of multiple random walks.