Nonadaptive group testing involves grouping arbitrary 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 constraints on pooling is imposed. Specifically, if $T(n)$ corresponds to the mixing time of the graph $G$ , it is shown that with $m=O(d2T2(n)\log(n/d))$ nonadaptive tests, one can identify the defective items. Consequently, for the Erds-Rényi random graph $G(n,p)$, as well as expander graphs with constant spectral gap, it follows that $m=O(d2\log3n)$ nonadaptive 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\log3n)$ nonadaptive 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.
Bibliographical noteFunding Information:
Manuscript received May 19, 2010; revised June 15, 2011; accepted July 07, 2011. Date of current version January 06, 2012. Part of this research was done while M. Cheraghchi and S. Mohajer were with the School of Computer and Communication Sciences, EPFL, Switzerland. M. Cheraghchi was supported by the ERC Advanced Investigator Grant 228021 of A. Shokrollahi. S. Mohajer was supported by ERC Starting Investigator Grant 240317. V. Saligrama was supported in part by the U.S. Department of Homeland Security under Award Number 2008-ST-061-ED0001, in part by NSF CPS Award 0932114, and in part by NSF CAREER Award Number ECS 0449194. The material in this paper was presented in part at the 2010 IEEE International Symposium on Information Theory. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security, or the U.S. National Science Foundation.
Dr. Saligrama has been an Associate Editor for IEEE TRANSACTIONS ON SIGNAL PROCESSING and is currently serving as a member on the Signal Processing Theory and Methods committee. He is the recipient of numerous awards including the Presidential Early Career Award, ONR Young Investigator Award, and the NSF Career Award.
- Group testing
- network tomography
- random walks
- sensor networks
- sparse recovery