An adaptive algorithm for group testing for complexes

In group testing for complexes, the property of being positive is not defined on single items but on subsets of items. Given a set N of n items with at most d positive subsets of N, each positive subset having cardinality at most r  , we need to determine the set P⊂P(N)P⊂P(N) of positive subsets via group tests. In this paper, we give an adaptive algorithm for group testing for the complex model, for all r≥2r≥2, which can be seen as a generalization of the binary splitting method for classical group testing (r=1r=1). For fixed r  , our algorithm solves the problem with O(drlog⁡n)O(drlog⁡n) tests while the best known non-adaptive algorithm requires O(dr+1(1+3/d)dlog⁡nd) tests. While non-adaptive solutions are preferable for some applications that require parallelization of tests, our adaptive algorithm is superior when d grows with n, yielding a polynomial number of tests on d   and log⁡klog⁡k.