Edge search in hypergraphs (Q1356674)

Consider a hypergraph \(H=(X,E)\) with a probability distribution \(P\) on the set \(E\) of its hyperedges. The authors study the average case complexity \(\overline L(H,P)\) of finding an unknown hyperedge \(e^*\in E\), chosen according to \(P\), if allowed tests are only those that check whether \(e^*\) is contained in the induced subhypergraph \(H[Y]\) for \(Y\subset X\) or not. They show that \(H(P) \leq\overline L(H,P)\leq H(P) +3r\) where \(H(P)\) is the entropy function and \(r=\sum_{e\in E} P(e)|e|\).