Searching for an edge in a graph with restricted test sets

Consider the (2,n)(2,n) group testing problem with test sets of cardinality at most 2. We determine the worst case number c2c2 of tests for this restricted group testing problem.Furthermore, using a game theory approach we solve the generalization of this group testing problem to the following search problem, which was suggested by Aigner in [M. Aigner, Combinatorial Search, Wiley-Teubner, 1988]: Suppose a graph G(V,E)G(V,E) contains one defective edge ee. We search for the endpoints of ee by asking questions of the form “Is at least one of the vertices of XX an endpoint of ee?”, where XX is a subset of VV with |X|≤2|X|≤2. What is the minimum number c2(G)c2(G) of questions, which are needed in the worst case to identify ee?We derive sharp upper and lower bounds for c2(G)c2(G). We also show that the determination of c2(G)c2(G) is an NP-complete problem. Moreover, we establish some results on c2c2 for random graphs.