An adaptive algorithm for group testing for complexes

作者：Chodoriwsky Jacob; Moura Lucia^*

来源：Theoretical Computer Science, 2015, 592: 1-8.

DOI：10.1016/j.tcs.2015.05.005

• Combinatorial group testing
• Complex group testing
• Graph testing
• Hypergraph testing

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 subset of 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 <= 2, which can be seen as a generalization of the binary splitting method for classical group testing (r = 1). For fixed r, our algorithm solves the problem with O (d(r) logn) tests while the best known non-adaptive algorithm requires O (d(r+1)(1+3/d)(d) log n/d)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 logk.

• 出版日期2015-8-9