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.
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: