Strict Group Testing and the Set Basis Problem

Damaschke, Peter and Muhammad, Azam Sheikh and Wiener, Gábor (2014) Strict Group Testing and the Set Basis Problem. JOURNAL OF COMBINATORIAL THEORY SERIES A, 126. pp. 70-91. ISSN 0097-3165

Text gtstrj.pdf - Accepted Version Restricted to Registered users only Download (300kB) | Request a copy

Abstract

Group testing is the problem to identify up to d defectives out of n elements, by testing subsets for the presence of defectives. Let t(n, d, s) be the optimal number of tests needed by an s-stage strategy in the strict group testing model where the searcher must also verify that at most d defectives are present. We start building a combinatorial theory of strict group testing. We compute many exact t(n, d, s) values, thereby extending known results for s = 1 to multistage strategies. These are interesting since asymptotically nearly optimal group testing is possible already in s = 2 stages. Besides other combinatorial tools we generalize d-disjunct matrices to any candidate hypergraphs, and we reveal connections to the set basis problem and communication complexity. As a proof of concept we apply our tools to determine almost all test numbers for n ≤ 10 and some further t(n, 2, 2) values. We also show t(n, 2, 2) ≤ 2.44 log^2 n + o(log^2 n).

Actions (login required)

Edit Item