An Almost Optimal Algorithm for Generalized Threshold Group Testing with Inhibitors

Abstract

Group testing is a search paradigm where one is given a population S of n elements and an unknown subset P subset of S of defective elements and the goal is to determine P by performing tests on subsets of S. In classical group testing a test on a subset Q subset of S receives a YES response if vertical bar Q boolean AND P vertical bar >= 1, and a NO response otherwise. In group testing with inhibitors (GTI), identifying the defective items is more difficult due to the presence of elements called inhibitors that interfere with the queries so that the answer to a query is YES if and only if the queried group contains at least one defective item and no inhibitor. In the present article, we consider a new generalization of the GTI model in which there are two unknown thresholds h and g and the response to a test is YES both in the case when the queried subset contains at least one defective item and less than h inhibitors, and in the case when the queried subset contains at least g defective items. Moreover, our search model assumes that no knowledge on the number vertical bar P vertical bar of defective items is given. We derive lower bounds on the minimum number of tests required to determine the defective items under this model and present an algorithm that uses an almost optimal number of tests.