An NP-Completeness Result of Edge Search in Graphs

Abstract

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 cp(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 cp(G). In the present paper we show that the computation of cp(G) is an NP-complete problem. In addition, we establish some results on cp(G) for random graphs.