Cover-free families on hypergraphs and combinatorial group testing

Combinatorial group testing (CGT) is used to identify a subset of defective items from a set of items by grouping them together and performing a small number of tests on the groups. Cover-free families (CFFs), also called superimposed codes, are well-studied combinatorial structures used to design the groups in such a way that identifying the defective items from test results (decoding) can be done efficiently. This paper focuses on generalizations of CFFs that take into account a known structure among items to be tested. This structure is modeled by a hypergraph, where vertices are items to be tested and edges represent a predictable relationship among items. A typical application is testing for an infectious disease in a population where there are clusters of individuals with high contact rates, such as households within a neighbourhood or students taking courses within a school. As we aim at minimizing the number of tests, CFFs on hypergraphs yield an interesting combinatorial optimization problem and, like CFFs, have connections to coding theory, design theory and extremal set theory. In this paper, we discuss various types of CFFs on hypergraphs, decoding algorithms, bounds and constructions. In particular, we give several constructions that use the structure and properties of the underlying hypergraph.