TY - GEN

T1 - Graph-constrained group testing

AU - Cheraghchi, Mahdi

AU - Karbasi, Amin

AU - Mohajer, Soheil

AU - Saligrama, Venkatesh

PY - 2010

Y1 - 2010

N2 - Non-adaptive group testing involves grouping arbitrary subsets of n items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagation we formulate non-adaptive group testing problems on graphs. Unlike conventional group testing problems each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper we associate a test with a random walk. In this context conventional group testing corresponds to the special case of a complete graph on n vertices. For interesting classes of graphs we arrive at a rather surprising result, namely, that the number of tests required to identify d defective items is substantially similar to that required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph G, we show that with m = O(d 2T2(n) log(n/d)) non-adaptive tests, one can identify the defective items. Consequently, for the Erdos-Rényi random graph G(n, p), as well as expander graphs with constant spectral gap, it follows that m = O(d2 log3 n) non-adaptive tests are sufficient to identify d defective items. We next consider a specific scenario that arises in network tomography and show that m = O(d3 log3 n) non-adaptive tests are sufficient to identify d defective items. We also consider noisy counterparts of the graph constrained group testing problem and develop parallel results for these cases.

AB - Non-adaptive group testing involves grouping arbitrary subsets of n items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagation we formulate non-adaptive group testing problems on graphs. Unlike conventional group testing problems each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper we associate a test with a random walk. In this context conventional group testing corresponds to the special case of a complete graph on n vertices. For interesting classes of graphs we arrive at a rather surprising result, namely, that the number of tests required to identify d defective items is substantially similar to that required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph G, we show that with m = O(d 2T2(n) log(n/d)) non-adaptive tests, one can identify the defective items. Consequently, for the Erdos-Rényi random graph G(n, p), as well as expander graphs with constant spectral gap, it follows that m = O(d2 log3 n) non-adaptive tests are sufficient to identify d defective items. We next consider a specific scenario that arises in network tomography and show that m = O(d3 log3 n) non-adaptive tests are sufficient to identify d defective items. We also consider noisy counterparts of the graph constrained group testing problem and develop parallel results for these cases.

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

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

U2 - 10.1109/ISIT.2010.5513397

DO - 10.1109/ISIT.2010.5513397

M3 - Conference contribution

AN - SCOPUS:77955675382

SN - 9781424469604

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1913

EP - 1917

BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings

T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010

Y2 - 13 June 2010 through 18 June 2010

ER -