On combinatorial search problems which involve graphs

Combinatorial search problems are represented as follows: An finite set M is searched for an object x by selecting a subset of a finite set of tests F such that they identify x uniquely. In this thesis 3 types of search problems are treated by solving some special problems involving graphs as structural element:1. The decision problem for graph properties.2. Group tests on graphs/hypergraphs in the sequential case.3. Group tests on graphs in the predetermined case.These problems require a specification of the set M according to the related problem. But more important is the influence on the set of admitted test functions F by the use of graphs by which one intends to find interesting restrictions on F. (I.e.: they should need some interesting mathematics, but also yield some results by not being to complex and unmanageable.) We always restrict to a binary answer (0/1 or yes/no ...). We look for a method to construct a subset of F that identifies x. Any algorithm is only allowed to compute the subset due to the known facts of the model. x, of cause, is unknown. A main question is, for example, whether the the algorithm is sequential or predetermined: in the first case, the answers of the former questions can be used to compute the next in a sequence. In the latter case, all questions have to be chosen before getting the answers.1. A graph property is a subset of graphs on a fixed vertex set of n vertices, the set being invariant under permutation of the vertices. An unknown graph G is to be tested for having property P. The admissible questions are "Is e an an edge of G?" for all possible edges, i.e. sets of vertices with two elements. If for every sequential algorithm there is a graph G (called the worst case )such that we have to test all edges to decide whether G is in P, then P is called evasive. It is a long standing conjecture that all monotone nontrivial graph properties are evasive. This conjecture is settled in the case n=p^k, p prime (Kahn et al.). Also an asymptotic bound for the necessary number of questions is known, but it is a relatively weak bound. In this thesis an improvement of this bound is shown. The topological methods of the prime case and asymptotic case are used in a neat proof. Moreover, I illustrate the use of computers in attacking evasiveness. 2. A group test is a search for a subset D of a set X. Depending on the model, there are some sets Y, subsets of X, that represent questions of the form "Is the intersection of D and Y empty?" When using the edges of a graph/hypergraph as the set X, each possible set Y is defined by some vertices such that Y is the set of edges only incident with these vertices. There is a conjecture of Du and Hwang (generalized to hypergraphs) describing a bound of the number of questions in the worst case and containing a constant c which is conjectured to exist. There is an algorithm in the case of graphs proving the conjecture for a constant c. I give a simpler algorithm and a better bound. Moreover, the hope is to generalize this algorithm to hypergraphs and prove the conjecture. I intended to give concrete hints where the obstacles to the generalization lie.3. The model is this of section 2, but |D|=1 and with the strong restriction to predetermined algorithms. This changes the situation entirely: only a weak bound for the number of questions needed in the worst case, and only for some special graphs G good bounds are known. Although the case "G is bipartite and complete" is almost trivial and can be shown to be (quasi) optimal, there is no bound for bipartite graphs, even in the seemingly simple case of G being a tree. Yet I found a good bound in this case as I think. The proof is in no way trivial. I think it is an interesting application of combinatorial and graph theoretic methods. Furthermore, it suggests that it is hard to find a much simpler algorithm for that bound. Finally, I show that the conjectured optimality (i.e., the minimum number of questions is that information theory gives us) cannot be shown with the idea of the proof.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2007

Author dc:creator

• Korneffel, Torsten

Contributors dc:contributor

• Triesch, Eberhard

• info:eu-repo/classification/ddc/510
• Kombinatorik
• Kombinatorisches Suchverfahren
• Suchverfahren
• Gruppentesten
• Graphentheorie
• Kombinatorische Graphentheorie
• Mathematik
• Entscheidungsproblem
• Evasivität
• evasiveness
• predetermined search
• sequential search

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

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

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:61713