ECCC-Report TR03-076https://eccc.weizmann.ac.il/report/2003/076Comments and Revisions published for TR03-076en-usThu, 16 Oct 2003 17:21:51 +0200
Paper TR03-076
| Testing the independence number of hypergraphs |
Michael Langberg
https://eccc.weizmann.ac.il/report/2003/076A $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$).
Thu, 16 Oct 2003 17:21:51 +0200https://eccc.weizmann.ac.il/report/2003/076