TY - JOUR
T1 - Identifying defective sets using queries of small size
AU - Benevides, Fabrício S.
AU - Gerbner, Dániel
AU - Palmer, Cory T.
AU - Vu, Dominik K.
N1 - Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/1
Y1 - 2018/1
N2 - We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set X of n elements we want to identify an unknown subset Y of X, which is known to have exactly d elements, by means of testing, for as few as possible subsets A of X, whether A intersects Y or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number k. Our main results are nearly tight bounds on the minimum number of tests necessary when d and k are fixed and n is large enough.
AB - We examine the following version of a classic combinatorial search problem introduced by Rényi: Given a finite set X of n elements we want to identify an unknown subset Y of X, which is known to have exactly d elements, by means of testing, for as few as possible subsets A of X, whether A intersects Y or not. We are primarily concerned with the non-adaptive model, where the family of test sets is specified in advance, in the case where each test set is of size at most some given natural number k. Our main results are nearly tight bounds on the minimum number of tests necessary when d and k are fixed and n is large enough.
KW - Combinatorial search
KW - Group testing
KW - Separable hypergraphs
KW - Union-free hypergraphs
UR - http://www.scopus.com/inward/record.url?scp=85029163841&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2017.08.023
DO - 10.1016/j.disc.2017.08.023
M3 - Article
AN - SCOPUS:85029163841
SN - 0012-365X
VL - 341
SP - 143
EP - 150
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 1
ER -