SEARCH PROBLEMS ON GRAPHS

The determination of defective elements in a population by a series of group tests has received considerable attention. In this paper, the following natural generalization to graphs is studied. Given a graph G with vertex-set V and edge-set E, and an unknown edge e* epsilon E. In order to find e* we choose a sequence of test-sets A CONTAINS V, where after every test we are told whether e* has both end-vertices in A, one end-vertex, or lies outside. Find the minimum c(G) of tests required. c(G) is studied in detail for the complete graphs K//n and the complete bipartite graphs K//m,//n. Remarks are made on optimal graphs which achieve the information-theoretic lower bound and on a previously studied binary variant.