×

Strict group testing and the set basis problem. (English) Zbl 1407.05090

Summary: Group testing is the problem to identify up to \( d\) defectives out of \( n\) elements, by testing subsets for the presence of defectives. Let \(t(n, d, s)\) be the optimal number of tests needed by an \( s\)-stage strategy in the strict group testing model where the searcher must also verify that at most \( d\) defectives are present. We start building a combinatorial theory of strict group testing. We compute many exact \(t(n, d, s)\) values, thereby extending known results for \(s = 1\) to multistage strategies. These are interesting since asymptotically nearly optimal group testing is possible already in \(s = 2\) stages. Besides other combinatorial tools we generalize \(d\)-disjunct matrices to any candidate hypergraphs, and we reveal connections to the set basis problem and communication complexity. As a proof of concept we apply our tools to determine almost all test numbers for \(n \leq 10\) and some further \(t(n, 2, 2)\) values. We also show \(t(n, 2, 2) \leq 2.44 \log_2 n + o(\log_2 n)\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C65 Hypergraphs
05B20 Combinatorial aspects of matrices (incidence, Hadamard, etc.)
62K10 Statistical block designs
68W20 Randomized algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Balding, D. J.; Torney, D. C., Optimal pooling designs with error detection, J. Combin. Theory Ser. A, 74, 131-140 (1996) · Zbl 0847.05030
[2] Bezrukov, S.; Fronček, D.; Rosenberg, S. J.; Kovář, P., On biclique coverings, Discrete Math., 308, 319-323 (2008) · Zbl 1135.05057
[3] Chen, H. B.; Hwang, F. K., Exploring the missing link among \(d\)-separable, \( \overline{d} \)-separable and \(d\)-disjunct matrices, Discrete Appl. Math., 155, 662-664 (2007) · Zbl 1119.15027
[4] Damaschke, P.; Sheikh Muhammad, A.; Triesch, E., Two new perspectives on multi-stage group testing, Algorithmica, 67, 324-354 (2013) · Zbl 1311.68187
[5] De Bonis, A.; Di Crescenco, G., Combinatorial group testing for corruption localizing hashing, (Fu, B.; Du, D. Z., COCOON 2011. COCOON 2011, Lecture Notes in Comput. Sci., vol. 6842 (2011), Springer: Springer Heidelberg), 579-591 · Zbl 1353.94046
[6] De Bonis, A.; Gasieniec, L.; Vaccaro, U., Optimal two-stage algorithms for group testing problems, SIAM J. Comput., 34, 1253-1270 (2005) · Zbl 1079.68043
[7] de Caen, D.; Gregory, D. A.; Pullman, N. J., The boolean rank of zero-one matrices, (Proc. 3rd Caribbean Conf. on Combinatorics and Computing (1981)), 169-173 · Zbl 0496.20052
[8] Du, D. Z.; Hwang, F. K., Combinatorial Group Testing and Its Applications, Ser. Appl. Math., vol. 3 (2000), World Scientific · Zbl 0867.90060
[9] Du, D. Z.; Hwang, F. K., Pooling Designs and Nonadaptive Group Testing, Ser. Appl. Math., vol. 18 (2006), World Scientific · Zbl 1284.62009
[10] D’yachkov, A. G., Lectures on Designing Screening Experiments, Lect. Notes Ser., vol. 10 (2003), Comb. and Comp. Math. Center, Pohang Univ. of Science and Technol.
[11] D’yachkov, A. G.; Macula, A. J.; Rykov, V. V., New constructions of superimposed codes, IEEE Trans. Inform. Theory, 46, 284-290 (2000) · Zbl 0999.94044
[12] D’yachkov, A. G.; Macula, A. J.; Rykov, V. V., New applications and results of superimposed code theory arising from the potentialities of molecular biology, (Numbers, Information and Complexity (2000), Kluwer), 265-282 · Zbl 1034.94015
[13] D’yachkov, A. G.; Rykov, V. V., Bounds on the length of disjunctive codes, Probl. Inf. Transm., 18, 166-171 (1982) · Zbl 0524.94015
[14] D’yachkov, A. G.; Rykov, V. V., A survey on superimposed code theory, Probl. Control Inf. Theor., 12, 229-242 (1983) · Zbl 0524.94016
[15] D’yachkov, A. G.; Rykov, V. V.; Rashad, A. M., Superimposed distance codes, Probl. Control Inf. Theor., 18, 237-250 (1989) · Zbl 0693.94005
[16] D’yachkov, A. G.; Vilenkin, P.; Rykov, V. V.; Torney, D., Families of finite sets in which no intersection of \(ℓ\) sets is covered by the union of \(s\) others, J. Combin. Theory Ser. A, 99, 195-218 (2002) · Zbl 1020.94027
[17] D’yachkov, A. G.; Vorobyev, I. V.; Polyanskii, N. A.; Shchukin, V. Y., Bounds on the rate of superimposed codes (2014), preprint · Zbl 1321.94124
[18] Eppstein, D.; Goodrich, M. T.; Hirschberg, D. S., Improved combinatorial group testing algorithms for real-world problem sizes, SIAM J. Comput., 36, 1360-1375 (2007) · Zbl 1124.68043
[19] Erdős, P.; Frankl, P.; Füredi, Z., Families of finite sets in which no set is covered by the union of two others, J. Combin. Theory Ser. A, 33, 158-166 (1982) · Zbl 0489.05003
[20] Fang, J.; Jiang, Z. L.; Yiu, S. M.; Hui, L. C.K., An efficient scheme for hard disk integrity check in digital forensics by hashing with combinatorial group testing, Int. J. Digital Content Technol. Appl., 5, 300-308 (2011)
[21] Fischer, P.; Klasner, N.; Wegener, I., On the cut-off point for combinatorial group testing, Discrete Appl. Math., 91, 83-92 (1999) · Zbl 0924.68170
[22] Fronček, D.; Jerebic, J.; Klavžar, S.; Kovář, P., Strong isometric dimension, biclique coverings, and Sperner’s theorem, Combin. Probab. Comput., 16, 271-275 (2007) · Zbl 1122.05033
[23] Gao, H.; Hwang, F. K.; Thai, M. T.; Wu, W.; Znati, T., Construction of d(H)-disjunct matrix for group testing in hypergraphs, J. Comb. Optim., 12, 297-301 (2006) · Zbl 1115.92019
[24] Goodrich, M. T.; Hirschberg, D. S., Improved adaptive group testing algorithms with applications to multiple access channels and dead sensor diagnosis, J. Comb. Optim., 15, 95-121 (2008) · Zbl 1182.94005
[25] (version as of January 2013)
[26] Huang, S. H.; Hwang, F. K., When is individual testing optimal for nonadaptive group testing?, SIAM J. Discrete Math., 14, 540-548 (2001) · Zbl 0984.05074
[27] Kautz, W. H.; Singleton, R. C., Nonrandom binary superimposed codes, IEEE Trans. Inform. Theory, 10, 363-377 (1964) · Zbl 0133.12402
[28] Kushilevitz, E.; Nisan, N., Communication Complexity (1997), Cambridge Univ. Press · Zbl 0869.68048
[29] Macula, A. J.; Reuter, G. R., Simplified searching for two defects, J. Statist. Plann. Inference, 66, 77-82 (1998) · Zbl 0890.05012
[30] Mézard, M.; Toninelli, C., Group testing with random pools: optimal two-stage algorithms, IEEE Trans. Inform. Theory, 57, 1736-1745 (2011) · Zbl 1366.62152
[31] Spencer, J., Minimal completely separating systems, J. Comb. Number Theory, 8, 446-447 (1970) · Zbl 0185.03201
[32] Stockmeyer, L. J., The set basis problem is NP-complete (1975), IBM, Tech. Report RC-5431
[33] Weideman, C. A.; Raghavarao, D., Some optimum non-adaptive hypergeometric group testing designs for identifying two defectives, J. Statist. Plann. Inference, 16, 55-61 (1987) · Zbl 0613.62100
[34] Xuan, Y.; Shin, I.; Thai, M. T.; Znati, T., Detecting application denial-of-service attacks: a group-testing-based approach, IEEE Trans. Parallel Distrib. Syst., 21, 1203-1216 (2010)
[35] Zhang, B., Group testing regression models (2012), Dept. of Statistics, Univ. of Nebraska: Dept. of Statistics, Univ. of Nebraska Lincoln, Dissertation
[36] Zhang, G.; Cui, L., A set coverage problem, Inform. Process. Lett., 110, 158-159 (2010) · Zbl 1197.05156
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.