Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR03-076 | 8th September 2003 00:00

Testing the independence number of hypergraphs


Authors: Michael Langberg
Publication: 16th October 2003 17:21
Downloads: 2279


A $k$-uniform hypergraph $G$ of size $n$ is said to be $\varepsilon$-far from having an independent set of size $\rho n$ if one must remove at least $\varepsilon n^k$ edges of $G$ in order for the remaining hypergraph to have an independent set of size $\rho n$. In this work, we present a natural {\em property testing} algorithm that distinguishes between hypergraphs which have an independent set of size $\geq \rho n$ and hypergraphs which are $\varepsilon$-far from having an independent set of size $\rho n$. Our algorithm is natural in the sense that we sample $\simeq c(k)\frac{\rho^{2k}}{\varepsilon^3}$ random vertices of $G$, and according to the independence number of the hypergraph induced by this sample, we distinguish between the two cases above. Here $c(k)$ depends on $k$ alone ({\em e.g.} the sample size is independent of $n$).

ISSN 1433-8092 | Imprint