1Graph-Constrained Group Testing

Abstract—Non-adaptive group testing involves grouping ar-bitrary subsets of n items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most d defective items. Motivated by applications in network tomography, sensor networks and infection propagation, a variation of group testing problems on graphs is formulated. 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, a test is associated 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 a rather surprising result is obtained, namely, that the number of tests required to identify d defective items is substantially similar to what is required in conventional group testing problems, where no such con-straints on pooling is imposed. Specifically, if T (n) corresponds to the mixing time of the graph G, it is shown that with m = O(d2T 2(n) log(n/d)) non-adaptive tests, one can identify the defective items. Consequently, for the Erdős-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. Next, a specific scenario is considered that arises in network tomography, for which it is shown that m = O(d3 log3 n) non-adaptive tests are sufficient to identify d defective items. Noisy counterparts of the graph constrained group testing problem are considered, for which parallel results are developed. We also briefly discuss extensions to compressive sensing on graphs