Non-adaptive Group Testing on Graphs

In the classic group testing problem which was first introduced by Dorfman [11], there is a set ofnitems including at most d defective items. The purpose of this problem is to find the defective items with the minimum number of tests. Every test consists of some items and each test is positive if it includes at least one defective item. Otherwise, the test is negative. There are two types of algorithms for the group testing problem, adaptive and non-adaptive. In adaptive algorithm, the outcome of previous tests can be used in the future tests and in non-adaptive algorithm all tests perform simultaneously and the defective items are obtained by considering results of all tests. Regarding some extensions of classical group testing, we can refer to group testing on graphs, complex group testing, additive model, inhibitor model, etc. (see [12, 13, 17] for more information). Aigner [1] proposed the problem of group testing on graphs, in which we look for one defective edge of the given graphGby performing the minimum adaptive tests, where each test is an induced subgraph of the graph G and the test is positive in the case of involving the defective edge.