How to Color Graphs, and How Not to Chase Pointers

Abstract

We present several results in the graph streaming and number-in-hand communication models.

In the graph streaming model, the edges of the input graph stream by one-by-one, and the algorithm must process this stream with limited memory, which is significantly smaller than required to store the entire graph. Brooks' Theorem states that a graph with maximum degree Δ can be Δ-colored as long as it is not a clique or an odd-cycle. We show a 1-pass, O(n polylog(n)) space algorithm that can Δ-color a graph given as a stream. This is optimal up to log n factors.

In the number-in-hand communication model, the input to some relation is partitioned between k players, who work together to compute an output to the relation while minimizing the number of bits they communicate to each other. We have three results in this model.

First, we show an O(n) communication protocol that can (Δ + 1)-color a graph, whose edges are partitioned between two players. This is optimal up to constant factors.

Our second and third results are about the pointer chasing problem. In the pointer chasing problem, two players receive functions from [n] → [n], and wish to find the sequence of elements of [n] obtained by applying their functions alternately k times on the starting element 1. We show that any k / 1000 round communication protocol that solves this task must use Ω(n) communication. This lower bound is optimal up to factors of log n.

We also show an optimal lower bound for any (k - 1) round protocol that solves a version of this problem where each value of the input functions is further obscured behind a set intersection instance.