CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Competitive group testing and learning hidden vertex covers with minimum adaptivity

Peter Damaschke (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers)) ; Azam Sheikh Muhammad (Institutionen för data- och informationsteknik, Datavetenskap, Algoritmer (Chalmers))
Discrete Mathematics, Algorithms and Applications (1793-8309). Vol. 2 (2010), 3, p. 291-311.
[Artikel, refereegranskad vetenskaplig]

Suppose that we are given a set of n elements d of which have a property called defective. A group test can check for any subset, called a pool, whether it contains a defective. It is known that a nearly optimal number of O(d log (n/d)) pools in 2 stages (where tests within a stage are done in parallel) are sufficient, but then the searcher must know d 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 beforehand. We prove a lower bound of O(log d log log d) stages and a more general pools vs. stages tradeoff. This is almost tight, since O(log d) stages are sufficient for a strategy with O(d log n) pools. As opposed to this negative result, we devise a randomized strategy using O(d log (n/d)) pools in 3 stages, with any desired success probability 1-epsilon. With some additional measures even 2 stages are enough. 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 parameterized algorithm for vertex cover enumeration as a decoder. During the course of this work we also provide a classification of types of randomized search strategies in general.

Nyckelord: nonadaptive group testing, competitive group testing, combinatorial search, randomization

Denna post skapades 2010-11-17. Senast ändrad 2015-02-11.
CPL Pubid: 129203