Non-adaptive Group Testing on Graphs

Grebinski and Kucherov (1998) and Alon et al. (2004-2005) study the problemof learning a hidden graph for some especial cases, such as hamiltonian cycle,cliques, stars, and matchings. This problem is motivated by problems inchemical reactions, molecular biology and genome sequencing. In this paper, we present a generalization of this problem. Precisely, weconsider a graph G and a subgraph H of G and we assume that G contains exactlyone defective subgraph isomorphic to H. The goal is to find the defectivesubgraph by testing whether an induced subgraph contains an edge of thedefective subgraph, with the minimum number of tests. We present an upper boundfor the number of tests to find the defective subgraph by using the symmetricand high probability variation of Lov\'asz Local Lemma