An NP-Completeness Result of Edge Search in Graphs

Consider the following generalization of the classical sequential group testing problem for two defective items: suppose a graph G contains n vertices two of which are defective and adjacent. Find the defective vertices by testing whether a subset of vertices of cardinality at most p contains at least one defective vertex or not. What is then the minimum number c _p (G) of tests, which are needed in the worst case to find all defective vertices? In Gerzen (Discrete Math 309(20):5932–5942, 2009), this problem was partly solved by deriving lower and sharp upper bounds for c _p (G). In the present paper we show that the computation of c _p (G) is an NP-complete problem. In addition, we establish some results on c _p (G) for random graphs.