Adaptive Graph-Constrained Group Testing
- 21 December 2021
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Signal Processing
- Vol. 70 (1053587X) , 381-396
Abstract
This paper considers the problem of adaptive group testing for the purpose of isolating up to k defective items from a population of size $n$ . There exist restrictions or preferences, based on which, each item can be pooled for testing only with a pre-specified set of items+. A graphical model is adopted to formalize pooling restrictions and preferences. Such graph-constrained group testing is investigated in three population settings: populations with defectives, populations facing the potential presence of inhibitors, and populations with community structures. Adaptive group testing frameworks are provided for each of these population settings. In populations without inhibitors, existing non-adaptive frameworks can isolate the defective items perfectly with $\Theta\left(k^2\varpi^2\log\frac{n}{k}\right)$ number of tests, where $\varpi$ is the $\beta$ -mixing time of a random walk over the underlying graph. This paper provides a two-stage framework that requires $\Theta\left(k \varpi^2\log\frac{n}{k} + k\right)$ number of tests for perfectly isolating up to k defective items for a regular graph, thus achieving an approximate gain of a factor of k over the non-adaptive frameworks. This two-stage framework's principles are extended to graphs with underlying communities and graphs with up to r inhibitor items. In particular, when the inhibitors are present in the graph, a four-stage group testing framework is proposed. The results show that in the regime $r= O(k)$ for a fully-connected graph, $\Theta((k+r)\log n/(k+r) + r\log n)$ tests are sufficient for isolating the defective items. This matches the corresponding necessary condition on tests which scales $(k+r)\log n$ . The adaptive graph-constrained group testing framework is empirically evaluated in a case study.
Keywords
Funding Information
- National Science Foundation (ECCS-1554482, DMS-1737976)
- RPI-IBM Artificial. Intelligence Research Center
- ARO (W911NF1910269)
- DOE (DE-SC0021417)
- Vetenskapsrådet (2018-04359)
- NSF (CCF-2008927)
- ONR (503400-78050)
This publication has 46 references indexed in Scilit:
- Group Testing-Based Spectrum Hole Search for Cognitive RadiosIEEE Transactions on Vehicular Technology, 2014
- Group Testing with Multiple Mutually-Obscuring Positives2013
- Randomized Group Testing Both Query-Optimal and Minimal Adaptive2012
- New combinatorial structures with applications to efficient group testing with inhibitorsJournal of Combinatorial Optimization, 2007
- Pooling Experiments for Blood Screening and Drug Discovery2006
- Almost Optimal Explicit Selectors2005
- Optimal Two-Stage Algorithms for Group Testing ProblemsSIAM Journal on Computing, 2005
- Network Tomography: Recent DevelopmentsStatistical Science, 2004
- Error-correcting nonadaptive group testing with de-disjunct matricesDiscrete Applied Mathematics, 1997
- A Two-Stage Adaptive Group-Testing Procedure for Estimating Small ProportionsJournal of the American Statistical Association, 1994