A competitive algorithm to find all defective edges in a graph
Consider a graph G(V,E) G ( V , E ) where a subset D?E D ? E is called the set of defective edges. The problem is to identify D with a small number of edge tests, where an edge test takes an arbitrary subset S  and asks whether the subgraph G(S) G ( S ) induced by S intersects D (contains a defective edge). Recently, Johann gave an algorithm to find all d  defective edges in a graph assuming d=|D| d = | D | is known. We give an algorithm with d  unknown which requires at most d ( ? log 2 | E | ? + 4 ) + 1 tests. The information-theoretic bound, knowing d , is about d log 2 ( | E | / d ) . For d fixed, our algorithm is competitive with coefficient 1.
competitive algorithm group testing graph testing