On Detecting Some Defective Items in Group Testing

Abstract Group testing is an approach aimed at identifying up to d defective items among a total of n elements. This is accomplished by examining subsets to determine if at least one defective item is present. We focus on the problem of identifying a subset of $$\ell < d$$ ℓ < d defective items. We develop upper and lower bounds on the number of tests required to detect $$\ell $$ ℓ defective items in both the adaptive and non-adaptive settings while considering scenarios where no prior knowledge of d is available, and situations where some non-trivial estimate of d is at hand. When d is unknown, we prove a lower bound of $$ \varOmega (\frac{\ell \log ^2n}{\log \ell +\log \log n})$$ Ω ( ℓ log 2 n log ℓ + log log n ) tests in the randomized non-adaptive settings and an upper bound of $$O(\ell \log ^2 n)$$ O ( ℓ log 2 n ) for the same settings. Furthermore, we demonstrate that any non-adaptive deterministic algorithm must make $$\varTheta (n)$$ Θ ( n ) tests, signifying a fundamental limitation in this scenario. For adaptive algorithms, we establish tight bounds in different scenarios. In the deterministic case, we prove a tight bound of $$\varTheta (\ell \log {(n/\ell )})$$ Θ ( ℓ log ( n / ℓ ) ) . Moreover, in the randomized settings, we derive a tight bound of $$\varTheta (\ell \log {(n/d)})$$ Θ ( ℓ log ( n / d ) ) . When d , or at least some non-trivial estimate of d , is known, we prove a tight bound of $$\varTheta (d\log (n/d))$$ Θ ( d log ( n / d ) ) for the deterministic non-adaptive settings, and $$\varTheta (\ell \log (n/d))$$ Θ ( ℓ log ( n / d ) ) for the randomized non-adaptive settings. In the adaptive case, we present an upper bound of $$O(\ell \log (n/\ell ))$$