Improved Bounds for Group Testing in Arbitrary Hypergraphs
摘要
In group testing, the problem is to determine the defective members of a given set of elements O by performing tests on properly selected subsets of O. A response to a test is “yes” if the tested group contains one or more defective elements, and is “no” otherwise. The classical model of group testing has been recently generalized in a way such that the potentially contaminated sets are the hyperedges of a given hypergraph \(\mathcal{F}=(V,E)\) . This model takes into account how social and geographical clusterings affect the spreading of contaminations. The paper studies group testing algorithms with little adaptiveness, i.e., algorithms where tests are performed in stages and all tests performed in the same stage are decided at the beginning of the stage. In particular, the paper presents the first two-stage algorithm that uses \(o(d\log |E|)\) tests for arbitrary hypergraphs with hyperedges of size at most d, and a three-stage algorithm that improves by a \(d^{1/6}\) factor on the number of tests of the best so far known three-stage algorithm. These algorithms are special cases of an s-stage algorithm designed for an arbitrary positive integer \(s\le d\) . The design of this algorithm resorts to a new non-adaptive algorithm (one-stage algorithm), i.e., an algorithm where all tests must be decided beforehand. A major contribution of the paper consists in a non-existential result for non-adaptive group testing. Remarkably, this result implies the first lower bound for non-adaptive group testing that improves on the information theoretic lower bound \(\varOmega (\log |E|)\) and gets very close to the number of tests used by the best non-adaptive group testing algorithm.