Edge search in graphs using incidence tests

  • Suche nach einer Kante im Graph mit Hilfe der Inzidenztests

Gerzen, Tatjana; Triesch, Eberhard (Thesis advisor)

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

Aachen, Techn. Hochsch., Diss., 2008


In this work we consider the $(2,n)$ group testing problem with test sets of cardinality at most $p$. We present sharp upper and lower bounds for the worst case number $c_p(2,n)$ of tests for this group testing problem and show that the maximum difference between the upper and lower bounds is 3. Furthermore we consider the following generalization of the $(2, n)$ group testing problem: We interpret the search domain $V$ as the vertex set of an arbitrary, finite, simple, undirected graph $G$ with edge set $E$ and search for two defect elements from $V$, i.e an unknown edge $e$ in $E$. We search for the endpoints of $e$ by asking questions of the form "Is at least one of the vertices of $X$ an endpoint of $e$?", where $X$ is a subset of $V$ with cardinality at most $p$. What is then the minimum number $c_p(G)$ of questions, which are needed in the worst case to find $e$? We solve this search problem suggested by M. Aigner by deriving lower and sharp upper bounds for $c_p(G)$. We show furthermore that the computation of $c_p(G)$ is an NP-complete problem. We prove that the decision problem whether the worst case p-complexity of a graph is smaller than an integer $k$ is an NP-complete problem even if we use the greedy strategy. In addition, we establish some probabilistic results for the greedy bound. Moreover, we elaborate on the tractable case $p=2$. We present exact results on $c_2$ for some graph classes. By means of these results we continue with the proof of sharp upper bound for the number of edges of $G$, which depends on $c_2(G)$. We characterize the graphs for which this bound is exact in several ways. As a conclusion we receive sharp lower bounds for $c_2(G)$. We also determine the 2-complexity of the complete graph and provide thus a sharp upper bound for $c_2(G)$ of an arbitrary graph $G$, partly characterizing the extreme case.