Trivial two-stage group testing for complexes using almost disjunct matrices. (Q1422408)

Given \(t\) items with \(k\) unknown positive ones, the group testing problem is asking to identify all \(k\) positive items with a less number of tests each of which is on a subset of items and tells whether the subset contains a positive item or not. Consider a hypergraph with all \(k\)-subsets as its hyperedges and \(t\) items as its vertices. All \(k\) positive items form a positive hyperedge. Each test would tell whether the tested subset is incident to the positive hyperedge or not. The problem studied in this paper is a generalization of dual group testing problem. First, each test outcome is whether a subset contains a positive hyperedge or not, which is a dual test model in group testing. Secondly, there is not only one positive hyperedge. In this paper, the authors present a two-stage algorithm for identifying all positive hyperedges. (The hyperedge is called complex in this paper.)