A group testing problem for graphs with several defective edges (Q1348382): Difference between revisions

Given a graph \(G=(V,E)\) and an unknown set \(D\subseteq E\) of `defective' edges Du and Hwang posed a conjecture in 1993 on the minimum number of `tests' on sets of vertices of \(G\) that are required to identify all edges in \(D\) where the outcome of a test on a set \(W\subseteq V\) is positive, if \(W\) spans at least one edge in \(D\) and negative else. For an integer \(l\leq |E|/2\) and an unknown number \(d=|D|\) of defective edges the author describes an algorithm \({\mathcal A}_l\) that identifies all edges in \(D\) using \( \lfloor d ( \lceil \log_2 l \rceil + 6 - \frac{1}{l}) +\frac{|E|}{l}+1 \rfloor \) tests. If \(d\) is known, one can choose \(l=\lfloor\frac{|E|}{d}\rfloor\) which leads to \(d(\lceil\log_2 \frac{|E|}{d}\rceil + 7)\) tests and settles the above-mentioned conjecture in the affirmative. The basic ingredients of the algorithm \({\mathcal A}_l\) are previously known results independently due to Damaschke and Triesch for the identification of one of several defective edges and an ingenious partition of \(V\). The algorithm is best-possible in the sense that the given bound differs from the information-theoretic lower bound on the number of tests only by a fixed multiple of \(d\).