We consider space-efficient algorithms for two-coloring n-uniform hypergraphs H = (V, E) in the streaming model, when the hyperedges arrive one at a time. It is known that any such hypergraph with at most 0.7 n ln n 2 n hyperedges has a two-coloring [4] , which can be found deterministically in polynomial time, if allowed full access to the input. • Let s D (v, q, n) be the minimum space used by a deterministic (one-pass) streaming algorithm that on receiving an n-uniform hypergraph H on v vertices and q hyperedges (q ≤ 0.7 n ln n 2 n ), produces a proper two-coloring of H. We show that s D (n 2 , q, n) = Ω(q/n). • Let s R (v, q, n) be the minimum space used by a randomized (one-pass) streaming algorithm that on receiving an n-uniform hypergraph H on v vertices and q hyperedges with high probability produces a proper two-coloring of H (or declares failure). We show that • We show that for any 4 ≤ t ≤ this shows that every n-uniform hypergraph with at most n 2 t vertices and 2 n−1 exp( t 8 ) hyperedges is two-colorable. The above results are inspired by the study of the number q(n), the minimum possible number of hyperedges in a n-uniform hypergraph that is not two-colorable. It is known that q(n) = Ω( n ln n 2 n ) and q(n) = O(n 2 2 n ). The lower bound (due to Radhakrishnan and Srinivasan [4]) has a corresponding algorithm to deterministically produce the two-coloring; the upper bound due to Erdős is obtained by picking about n 2 2 n hyperedges randomly from a vertex set of n 2 vertices. Our first result shows that no efficient deterministic streaming algorithm can match the performance of the algorithm in [4] ; the second result shows that there is, however, an efficient randomized algorithm for the task; the third result shows that that if the number of vertices is substantially smaller than n 2 , then every non-two-colorable hypergraph has significantly more than n 2 2 n hyperedges.
In the streaming model, the problem of coloring an n-uniform hypergraph using two colors has been studied in REF .
Hypergraph Two-Coloring in the Streaming Model
ArXiv
ArXiv
Mathematics Computer Science