On a Hypergraph Approach to Multistage Group Testing Problems

Abstract

Group testing is a well known search problem that consists in detecting up to $s$ defective elements of the set $[t]=\{1,\dots ,t\}$ by carrying out tests on properly chosen subsets of $[t]$. In classical group testing the goal is to find all defective elements by using the minimal possible number of tests. In this paper we consider multistage group testing. We propose a general idea how to use a hypergraph approach to searching defects. For the case $s=2$, we design an explicit construction, which makes use of $2{\log }_{2}t(1+o(1))$ tests in the worst case and consists of $4$ stages. For the general case $s>2$, we provide an explicit construction, which uses $(2s-1){\log }_{2}t(1+o(1))$ tests and consists of $2s-1$ rounds.

5 pages, IEEE conference

References in corpus (2)

• Lectures on Designing Screening Experiments
• Bounds on the rate of superimposed codes