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) ; Institutionen för data- och informationsteknik, Datavetenskap, Bioinformatik (Chalmers))
17th International Symposium on Fundamentals of Computation Theory FCT 2009, Lecture Notes in Computer Science (0302-9743). Vol. 5699 (2009), p. 84-95.
[Konferensbidrag, refereegranskat]

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 O(log d/log log 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. 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, with any FPT algorithm for vertex cover enumeration as a decoder.

Nyckelord: competitive group testing, nonadaptive strategy, adversary, randomization, vertex cover



Denna post skapades 2009-09-07. Senast ändrad 2016-07-22.
CPL Pubid: 97556