Streaming Algorithms for 2-Coloring Uniform Hypergraphs

We consider the problem of two-coloring

n

-uniform hypergraphs. It is known that any such hypergraph with at most

$\frac{1}{10}\sqrt{\frac{n}{\ln n}} 2^n$

hyperedges can be two-colored [7]. In fact, there is an efficient (requiring polynomial time in the size of the input) randomized algorithm that produces such a coloring. As stated [7], this algorithm requires random access to the hyperedge set of the input hypergraph. In this paper, we show that a variant of this algorithm can be implemented in the streaming model (with just one pass over the input), using space

O

(|

V

|

B

), where

V

is the vertex set of the hypergraph and each vertex is represented by

B

bits. (Note that the number of hyperedges in the hypergraph can be superpolynomial in |

V

|, and it is not feasible to store the entire hypergraph in memory.)

We also consider the question of the minimum number of hyperedges in non-two-colorable

n

-uniform hypergraphs. Erdős showed that there exist non-2-colorable

n

-uniform hypegraphs with

O

(

n

2

2

n

) hyperedges and Θ(

n

2

) vertices. We show that the choice Θ(

n

2

) for the number of vertices in Erdös’s construction is crucial: any hypergraph with at most

$\frac{2 n^2}{t}$

vertices and

$2^n\exp(\frac{t}{8})$

hyperedges is 2-colorable. (We present a simple randomized streaming algorithm to construct the two-coloring.) Thus, for example, if the number of vertices is at most

n

1.5

, then any non-2-colorable hypergraph must have at least

$2^n \exp(\frac{\sqrt{n}}{8}) \gg n^22^n$

hyperedges. We observe that the exponential dependence on

t

in our result is optimal up to constant factors.