No Access

COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY

PETER DAMASCHKE

Department of Computer Science and Engineering, Chalmers University, 41296 Göteborg, Sweden

Search for more papers by this author

and

AZAM SHEIKH MUHAMMAD

Department of Computer Science and Engineering, Chalmers University, 41296 Göteborg, Sweden

Search for more papers by this author

https://doi.org/10.1142/S179383091000067XCited by:26 (Source: Crossref)

Abstract

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 two 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 Ω(log d/log log d) stages and more general pools versus 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 three stages, with any desired success probability 1-ϵ. With some additional measures even two stages are enough. Open questions concern the optimal constant factors and practical implications. A related problem motivated by 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 one-stage strategy using O(k³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.

This is an extended version of a paper presented at the 17th International Symposium on Fundamentals of Computation Theory FCT 2009, Wroclaw, Lecture Notes in Computer Science, 5699 (Springer), pp. 84–95.

Keywords:

AMSC: 68Q17, 68Q32, 68Q87, 68W20

References

N. Alon and V. Asodi, SIAM J. Discr. Math. 18, 697 (2005), DOI: 10.1137/S0895480103431071. Crossref, Google Scholar
D. Angluin and J. Chen, J. Comput. Syst. Sci. 74, 546 (2008), DOI: 10.1016/j.jcss.2007.06.006. Crossref, Google Scholar
A. Bar-Noyet al., Discr. Appl. Math. 52, 29 (1994), DOI: 10.1016/0166-218X(92)00185-O. Crossref, Google Scholar
M. Bouvel, V. Grebinski and G. Kucherov, Combinatorial search on graphs motivated by bioinformatics applications, Proc. 31st Workshop on Graph-Theoretic Concepts in Computer Science WG 2005, LNCS 3787, ed. D. Kratsch (Springer, 2005) pp. 17–27. Google Scholar
H. B. Chen, H. L. Fu and F. K. Hwang, Optim. Lett. 2, 425 (2008), DOI: 10.1007/s11590-007-0070-5. Crossref, Google Scholar
H. B. Chen and F. K. Hwang, Discr. Appl. Math. 155, 662 (2007), DOI: 10.1016/j.dam.2006.10.009. Crossref, Google Scholar
J. Chen, I. A. Kanj and G. Xia, Improved parameterized upper bounds for vertex cover, 31st Symp. on Math. Foundations of Computer Science MFCS 2006, LNCS 4162, eds. R. Kralovic and P. Urzyczyn (Springer, 2006) pp. 238–249. Google Scholar
Y. Cheng and D. Z. Du, J. Comput. Biol. 15, 195 (2008), DOI: 10.1089/cmb.2007.0195. Crossref, Google Scholar
A. E. F. Clementi, A. Monti and R. Silvestri, Selective families, superimposed codes, and broadcasting on unknown radio networks, 12th Symposium on Discrete Algorithms SODA (2001) pp. 709–718. Google Scholar
G. Cormode and S. Muthukrishnan, ACM Trans. Database Syst. 30, 249 (2005), DOI: 10.1145/1061318.1061325. Crossref, Google Scholar
P. Damaschke, J. Comput. Syst. Sci. 67, 46 (2003), DOI: 10.1016/S0022-0000(03)00047-3. Crossref, Google Scholar
P. Damaschke, Theor. Comput. Sci. 351, 337 (2006), DOI: 10.1016/j.tcs.2005.10.004. Crossref, Google Scholar
P. Damaschke, Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries, Networks, to appear . Google Scholar
A. De Bonis, L. Gasieniec and U. Vaccaro, SIAM J. Comput. 34, 1253 (2005), DOI: 10.1137/S0097539703428002. Crossref, Google Scholar
D. Z. Du and F. K. Hwang , Pooling Designs and Nonadaptive Group Testing ( World Scientific , 2006 ) . Link, Google Scholar
D. Z. Du and H. Park, SIAM J. Comput. 23, 1019 (1994), DOI: 10.1137/S0097539793246690. Crossref, Google Scholar
D. Z. Duet al., SIAM J. Comput. 23, 82 (1994), DOI: 10.1137/S0097539792227612. Crossref, Google Scholar
A. G. Dyachkov and V. V. Rykov, Problems of Information Transmission 18, 7 (1982). Google Scholar
D. Eppstein, M. T. Goodrich and D. S. Hirschberg, SIAM J. Comput. 36, 1360 (2007), DOI: 10.1137/050631847. Crossref, Google Scholar
A. C. Gilbert, M. A. Iwen and M. J. Strauss, Group testing and sparse signal recovery, 42nd Asilomar Conf. on Signals, Systems, and Computers (2008) pp. 1059–1063. Google Scholar
M. T. Goodrich and D. S. Hirschberg, J. Combin. Optim. 15, 95 (2008), DOI: 10.1007/s10878-007-9087-z. Crossref, Google Scholar
A. B. Kahng and S. Reda, IEEE Trans. CAD Integr. Circuits Syst. 25, 533 (2006), DOI: 10.1109/TCAD.2005.854635. Crossref, Google Scholar
M. Lappe and L. Holm, Nature Biotech. 22, 98 (2003), DOI: 10.1038/nbt921. Crossref, Google Scholar
M. Ruszinkó, J. Combin. Theory A 66, 302 (1994). Crossref, Google Scholar
J. Schlaghoff and E. Triesch, Combin. Probab. Comput. 14, 191 (2005), DOI: 10.1017/S0963548304006649. Crossref, Google Scholar