Non-adaptive complex group testing with multiple positive sets

Given n items with at most d of them having a particular property (referred as positive items), a test on a selected subset of them is positive if and only if the subset contains at least one positive item. The non-adaptive group testing problem is to design how to group the items to minimize the number of tests required to identify all positive items in which all tests are performed in parallel. This problem is well-studied and algorithms exist that match the lower bound with a small gap of logd asymptotically. An important generalization of the problem is to consider the case that an individual positive item cannot make a test positive, but a combination of them (referred as positive subsets) can do. The problem is referred as the non-adaptive complex group testing. Assume that there are at most d positive subsets whose sizes are at most s, existing algorithms either require Ω(logsn) tests for general n or tests for some special values of n. However, the number of items in each test cannot be very small or very large in real situation. The above algorithms cannot be applied because there is no control on the number of items in each test. In this paper, we provide a novel and practical derandomized algorithm to construct the tests with two important properties. (1) Our algorithm requires only tests for all positive integers n which matches the upper bound on the number of tests when all positive subsets are singletons, i.e. s=1. (2) All tests in our algorithm can have the same number of tested items k (for any input parameter k). Thus, our algorithm can solve the problem with additional constraints on the number of tested items in each test, such as maximum or minimum number of tested items.