Competitive Group Testing and Learning Hidden Vertex Covers with Minimum Adaptivity
Peter Damaschke and Azam Sheikh Muhammad
Abstract
Suppose that we are given a set of n elements d of which are
"defective". A group test can check for any subset, called a pool,
whether it contains a defective. It is well known that d defectives can
be found by using O(d log n) pools. This nearly optimal number of pools
can be achieved in 2 stages, where tests within a stage are done in
parallel. But then d must be known in advance. Here we explore group
testing strategies that use a nearly optimal number of pools and a few
stages although d is not known to the searcher. One easily sees that
O(log d) stages are sufficient for a strategy with O(d log n) pools.
Here we prove a lower bound of Omega(log d/loglog d) stages and a more
general pools vs. stages tradeoff. As opposed to this, we devise a
randomized strategy that finds d defectives using O(d log (n/d)) pools
in 3 stages, with any desired probability 1-epsilon. Open questions
concern the optimal constant factors and practical implications. A
related problem motivated by, e.g., biological network analysis is to
learn hidden vertex covers of a small size k in unknown graphs by edge
group tests. (Does a given subset of vertices contain an edge?) We give
a 1-stage strategy using O(k^3 log n) pools, with any FPT algorithm for
vertex cover enumeration as a decoder.