On a group testing problem: Characterization of graphs with 2-complexity c2 c 2 and maximum number of edges
Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in [1]: Suppose a graph G G contains one defective edge e? e ? . Find the endpoints of e? e ? by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of e? e ? or not. What is then the minimum number c2(G) c 2 ( G ) of tests, which are needed in the worst case to identify e? e ? ? In Gerzen (2009) [10], this problem was partially solved by deriving sharp lower and upper bounds for c2(G) c 2 ( G ) . In addition, it was proved that the determination of c2(G) c 2 ( G ) is an NP-complete problem. Among others, it was shown that the inequality | E | ? 4 ( c 2 ? 1 2 ) + 4 = 2 c 2 2 ? 6 c 2 + 8 holds for graphs with 2-complexity c2 c 2 and the edge set E E . In the present paper, we study the class of graphs for which this inequality is sharp and characterize these graphs in several ways. We suppose that for those graphs the 2-complexity can be computed in polynomial time by means of this characterization.
group testing problem graph combinatorial search