Graph-Constrained Group Testing

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^2T^2(n)\log(n/d))$ non-adaptive tests, one can identify the defective items. Consequently, for the Erdos-Renyi random graph $G(n,p)$, as well as expander graphs with constant spectral gap, it follows that $m=O(d^2\log^3n)$ 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(d^3\log^3n)$ 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.