A TIGHT UPPER BOUND FOR GROUP-TESTING IN GRAPHS

Let e(G) denote the edge number of a graph G, and let t(G) be the wors t-case number of tests required for finding a ''defective edge'' in G via group testing. This parameter has been intensively studied by seve ral authors. The best general upper bound known before was t(G) less-t han-or-equal-to inverted right perpendicular log2 e(G) inverted left p erpendicular + 3. Here we prove t(G) less-than-or-equal-to inverted ri ght perpendicular log2 e(G) inverted left perpendicular + 1. This resu lt is tight in the sense that there exist infinitely many graphs with t(G) = inverted right perpendicular log2 e(G) inverted left perpendicu lar + 1. Moreover, our proof leads to a surprisingly simple efficient algorithm which computes for input G a test strategy needing at most i nverted right perpendicular log2 e(G) inverted left perpendicular + 1 tests.