Edge search in graphs using incidence tests

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₂ 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₂(G). We characterize the graphs for which this bound is exact in several ways. As a conclusion we receive sharp lower bounds for c₂(G). We also determine the 2-complexity of the complete graph and provide thus a sharp upper bound for c₂(G) of an arbitrary graph $G$, partly characterizing the extreme case.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2008

Author dc:creator

• Gerzen, Tatjana

Contributors dc:contributor

• Triesch, Eberhard

• info:eu-repo/classification/ddc/510
• Sequentielle Suche
• Graph
• Gruppentesten
• Mathematik
• Inzideztest
• Gruppentetsproblem
• Kantensuche
• inzidenztest
• grouptesting
• combinatorial search
• edge search

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-112982%22

OAI record oai:identifier

https://publications.rwth-aachen.de/oai2d?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Apublications.rwth-aachen.de%3A50436