Optimal Algorithms for Two Group Testing Problems, and New Bounds on Generalized Superimposed Codes

Two variants of the well-known group testing problem are considered. In the first variant a finite set of items O and an unknown subset PsubeO are given, and one wants to identify the set P by asking the least number of questions of the form "Is |QcapP|=1?", where QsubeO. This problem naturally arises in the design of efficient contention resolution algorithms for certain random multiple-access communication systems [Berger et al. "Random multiple-access communication and group testing," IEEE Trans. Commun., vol. 32, no. 7, pp. 769-779, 1984]. In the second variant of the problem, the answer to the question "Is |QcapP|=1?" is correctly YES if |QcapP|=1 and NO if |QcapP|=0", and it is left to a (possibly malicious) adversary otherwise. This model was introduced in [Damaschke, "Randomized group testing for mutually obscuring defectives", Inf. Process. Lett., vol. 67, pp. 131-135, 1998], in the context of chemical compound testing. In this correspondence several algorithms for these group testing problems are presented, trying to optimize different measures of performance: The overall number of tests performed by the algorithm, the number of stages in which tests can be arranged, and the decoding complexity of identifying the elements of P from tests outcomes. Some of the given algorithms are optimal with respect to more than one of the above criteria. Instrumental to the results presented in the correspondence are new and improved bounds on certain generalization of superimposed codes introduced in [Dyachkov and Rykov, "A generalization of superimposed codes and its application to the multiple-access channel", in Proc. 1984 IEEE Int. Symp. Inf. Theory, pp. 62-64], [De Bonis and Vaccaro, "Constructions of generalized superimposed codes with applications to group testing and conflict resolution in multiple access channels", Theoretic. Comput. Sci., vol. 306, no. 1-3, pp. 223-243, 2003] a result that it is believed to be of independent interest

I. Introduction to Our Work and Motivations

In group testing, the task is to determine the positive members of a set of objects by asking the least possible number of subset queries (tests) of the form “Does the subset contain a positive object?”. Group testing was originally introduced as a potential approach to economical mass blood testing [14]. Due to its basic nature it has been proved to find applications in a surprising variety of situations, including quality control in product testing [37], searching for files in storage systems [29], screening for experimental variables [33], efficient conflict resolution algorithms for multiple-access channels [4], [40], data compression [24], [25], computation of statistics in the data stream model [8], [9], testing for concentration of chemical and pathogenic contaminants [20]. Group testing has been recently applied to Computational Molecular Biology, where it is used for screening library of clones with hybridization probes [2], [5], and sequencing by hybridization [34], [35]. We refer to [1], [15], [22], [36] for an account of the fervent development of the area. Recent important work is contained in [10]. We also notice that the necessity of estimating the current and future status of AIDS epidemic has brought back the original motivations for group testing, and group testing procedures are currently employed for HIV prevalence estimation (see [43], [23], [42] and references therein quoted). Very recently, group testing has been applied to the important issue of data gathering in sensor networks [26]–[28].