TY - GEN

T1 - Streaming algorithms for 2-coloring uniform hypergraphs

AU - Radhakrishnan, Jaikumar

AU - Shannigrahi, Saswata

PY - 2011/9/1

Y1 - 2011/9/1

N2 - We consider the problem of two-coloring n-uniform hypergraphs. It is known that any such hypergraph with at most 1/10 √n/1n n 2n 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. Erdos showed that there exist non-2-colorable n-uniform hypegraphs with O(n2 2n) hyperedges and Θ(n2) vertices. We show that the choice Θ(n2) for the number of vertices in Erdös's construction is crucial: any hypergraph with at most 2n2/t vertices and 2n exp(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(√n/8) ≫ n22n hyperedges. We observe that the exponential dependence on t in our result is optimal up to constant factors.

AB - We consider the problem of two-coloring n-uniform hypergraphs. It is known that any such hypergraph with at most 1/10 √n/1n n 2n 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. Erdos showed that there exist non-2-colorable n-uniform hypegraphs with O(n2 2n) hyperedges and Θ(n2) vertices. We show that the choice Θ(n2) for the number of vertices in Erdös's construction is crucial: any hypergraph with at most 2n2/t vertices and 2n exp(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(√n/8) ≫ n22n hyperedges. We observe that the exponential dependence on t in our result is optimal up to constant factors.

KW - hypergraph coloring

KW - Property B

KW - randomized algorithm

KW - streaming algorithm

UR - http://www.scopus.com/inward/record.url?scp=80052118230&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22300-6_57

DO - 10.1007/978-3-642-22300-6_57

M3 - Conference contribution

AN - SCOPUS:80052118230

SN - 9783642222993

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 667

EP - 678

BT - Algorithms and Data Structures - 12th International Symposium, WADS 2011, Proceedings

T2 - 12th International Symposium on Algorithms and Data Structures, WADS 2011

Y2 - 15 August 2011 through 17 August 2011

ER -