Reconstruction of hidden graphs and threshold group testing

• Published in: Journal of combinatorial optimization 2011-08, Vol.22 (2), p.270-281
• Main Authors: Chang, Huilan, Chen, Hong-Bin, Fu, Hung-Lin, Shi, Chie-Huai
• Format: Article
• Language: English
• Subjects: Applied sciences; Combinatorics; Combinatorics. Ordered structures; Computer science; control theory; systems; Convex and Discrete Geometry; Exact sciences and technology; Graph theory; Information retrieval. Graph; Mathematical Modeling and Industrial Mathematics; Mathematics; Mathematics and Statistics; Operations Research/Decision Theory; Optimization; Probability and statistics; Sampling theory, sample surveys; Sciences and techniques of general use; Statistics; Theoretical computing; Theory of Computation
• ISSN: 1382-6905; 1573-2886
• DOI: 10.1007/s10878-010-9291-0

Classical group testing is a search paradigm where the goal is the identification of individual positive elements in a large collection of elements by asking queries of the form “Does a set of elements contain a positive one?”. A graph reconstruction problem that generalizes the classical group testing problem is to reconstruct a hidden graph from a given family of graphs by asking queries of the form “Whether a set of vertices induces an edge”. Reconstruction problems on families of Hamiltonian cycles, matchings, stars and cliques on n vertices have been studied where algorithms of using at most 2 n lg  n ,(1+ o (1))( n lg  n ),2 n and 2 n queries were proposed, respectively. In this paper we improve them to and n +lg  n , respectively. Threshold group testing is another generalization of group testing which is to identify the individual positive elements in a collection of elements under a more general setting, in which there are two fixed thresholds ℓ and u , with ℓ < u , and the response to a query is positive if the tested subset of elements contains at least u positive elements, negative if it contains at most ℓ positive elements, and it is arbitrarily given otherwise. For the threshold group testing problem with ℓ = u −1, we show that p positive elements among n given elements can be determined by using O ( p lg  n ) queries, with a matching lower bound.