Edge search in hypergraphs

✍ Scribed by Ingo Althöfer; Matthias Löwe

• Book ID: 103061876
• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 231 KB
• Volume: 162
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00291-4

✦ Synopsis

Consider an undirected hypergraph H = (X, E) with a probability distribution P on the set E of its hyperedges. We investigate the average case complexity L(H, P) of finding an unknown hyperedge e*e E, chosen according to P, if only tests are allowed that check, whether e* is contained in the induced subhypergraphs H [Y] for Y c X, or not.

In this note we prove that for hypergraphs with average size of the hyperedges r H(P) <<, L(H, P) < H(P) + 3r. Here H(') denotes the usual entropy function. The lower bound is the information theoretic bound, whereas the upper bound stems from a construction presented in this note. More precisely, our construction gives search lengths which are bounded from above by -log2P(e* ) + 3-le*l for all possible choices of e*.