A group testing problem for graphs with several defective edges
In their book on group testing Du and Hwang (Combinatorial Group testing and its Applications, World Scientific, Singapore, 1993) considered the following generalization of classical group testing problems: Suppose a graph contains m edges d of which are defective. Find all defective edges by testing whether an induced subgraph contains a defective edge or not. They conjectured that this can be done by using at most
grouptesting searchproblems information theoretic lower bound