Non-adaptive Group Testing on Graphs

作者：Kameli Hamid^*

来源：Discrete Mathematics and Theoretical Computer Science, 2018, 20(1).

• Group testing on graphs
• Non-adaptive algorithm
• Combinatorial search
• Learning a hidden subgraph

Grebinski and Kucherov (1998) and Alon et al. (2004-2005) studied the problem of learning a hidden graph for some especial cases, such as hamiltonian cycle, cliques, stars, and matchings, which was motivated by some problems in chemical reactions, molecular biology and genome sequencing. The present study aims to present a generalization of this problem. Graphs G and H were considered, by assuming that G includes exactly one defective subgraph isomorphic to H. The purpose is to find the defective subgraph by performing the minimum non-adaptive tests, where each test is an induced subgraph of the graph G and the test is positive in the case of involving at least one edge of the defective subgraph H. We present the first upper bound for the number of non-adaptive tests to find the defective subgraph by using the symmetric and high probability variation of Lovasz Local Lemma Finally, we present the first non-adaptive randomized algorithm that finds the defective subgraph by at most 4 times of this upper bound with high probability.

• 出版日期2018