A tight upper bound for group testing in graphs

AbstractLet e(G) denote the edge number of a graph G, and let t(G) be the worst-case number of tests required for finding a “defective edge” in G via group testing. This parameter has been intensively studied by several authors. The best general upper bound known before was t(G) ≤ ⌈log2 e(G)⌉ + 3.Here we prove t(G) ≤ ⌈log2 e(G)⌉ + 1. This result is tight in the sense that there exist infinitely many graphs with t(G) = ⌈log2 e(G)⌉ + 1.Moreover, our proof leads to a surprisingly simple efficient algorithm which computes for input G a test strategy needing at most ⌈log2 e(G)⌉ + 1 tests