Searching for many defective edges in hypergraphs

• Suchen nach vielen defekten Kanten in Hypergraphen

Emonts, Jessica; Triesch, Eberhard (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2013)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2013

Abstract

Suppose we are given a hypergraph H = (V,E). Some of the edges in H have a distinguished property, we call these edges defective edges and denote their set by D. To find the defective edges, we use so called group tests. A group test tells us for any vertex set whether at least one defective edge lies completely in the vertex set or not. In the present work we investigate the number of tests that a sequential algorithm (all tests are stated one after the other and in dependence of the previous answers) needs in the worst case to find all defective edges. Is at the beginning of the search known that exactly d edges are defective, then there are |E|! / (d!•(|E|-d)!)) possibilities to choose D. In the worst case, per test not more than half the possibilities are excluded, thus any search algorithm needs in the worst case at least log2(|E|! / (d!•(|E|-d)!)) tests to find all defective edges. This lower bound is the information theoretic bound and is the best known lower bound for the group testing problem on hypergraphs. The best known upper bound was proven by Chen and Hwang in 2007. They showed that there is a search algorithm that needs in the worst case not more than d • ceil(log2(|E|))+(r-1)^ceil( r/2 ) • d^r+o(d^r) tests to find all defective edges in a hypergraph of rank <=r. At first we state a sharper lower bound, therefore we construct a hypergraph of rank r with defective edge set D, |D| = d, so that in the worst case the defective edges cannot be found with less than d • log2(|E|) + (1/r)^r/2 • d^r/2 tests. Thereafter we present a search algorithm, that finds all defective edges in a hypergraph of rank 3 with at most d •ceil(log2|E|)+ 2sqrt(d) + 10d + 24d^3/2 tests. Then we give an algorithm for general hypergraphs of rank r, that finds all defective edges by at most d •ceil(log2|E|)+ O(d^r/2) tests. In the last part of the thesis we consider the special case of 3-uniform hypergraphs. We introduce an algorithm that finds all defective edges with at most d •ceil(log2 (|E|/d))+ O(d) tests. Which proves for 3-uniform hypergraphs a conjecture of Du and Hwang.

Institutions

• Department of Mathematics [110000]
• Chair of Mathematics II (for Engineers) [113210]