On combinatorial search problems which involve graphs

Korneffel, Torsten; Triesch, Eberhard

doi:HT015058710

On combinatorial search problems which involve graphs = Über kombinatorische Suchprobleme, die Graphen beinhalten

Korneffel, Torsten (Author)

2007

Verantwortlichkeitsangabevorgelegt von Torsten Korneffel

ImpressumAachen : Publikationsserver der RWTH Aachen University 2007

UmfangVIII, 60 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2006

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Triesch, Eberhard (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2007-02-08

Online
URN: urn:nbn:de:hbz:82-opus-18099
URL: https://publications.rwth-aachen.de/record/61713/files/Korneffel_Torsten.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Kombinatorik (Genormte SW) ; Kombinatorisches Suchverfahren (Genormte SW) ; Suchverfahren (Genormte SW) ; Gruppentesten (Genormte SW) ; Graphentheorie (Genormte SW) ; Kombinatorische Graphentheorie (Genormte SW) ; Mathematik (frei) ; Entscheidungsproblem (frei) ; Evasivität (frei) ; evasiveness (frei) ; predetermined search (frei) ; sequential search (frei)

Thematische Einordnung (Klassifikation)
DDC: 510
msc: 05C65 05C3

Kurzfassung
Kombinatorische Suchprobleme werden auf folgende Weise modelliert: Es wird nach einem Objekt x aus einer endlichen Menge M gesucht, indem man aus einer endlichen Menge von Tests F eine Teilmenge auswählt, so dass x eindeutig durch diese Tests identifiziert wird. In der Dissertation werden Fragen zu 3 konkreten Arten von Suchproblemen behandelt, wobei jede für sich mit Graphen zu tun hat:1. Das Entscheidungsproblem für Grapheneigenschaften.2. Gruppentests auf Graphen/Hypergraphen im sequentiellen Fall.3. Gruppentests auf Graphen im predeterminierten Fall.Die Problemstellungen bedingen eine speziellere Definition der Menge M, die durch equivalente Begriffe ersetzt wird. Vorallem aber die Menge der möglichen Tests F wird durch die Verwendung von Graphen beeinflusst. Der Grund für die Idee, Graphen zu benutzen, ist, dass sie akzeptable und trotzdem möglichst interessante Einschränkung von F liefern sollen. Die Mengen A ist in allen drei Problemstelungen zweielementig, etwa interpretiert als ja,nein oder {1,0}. Gesucht ist eine Methode, die indentifizierende Teilmenge von F, gesehen als Reihe von Tests, zu finden. Einem Algorithmus ist es natürlich nur erlaubt, aufgrund der im Modell vorgegeben Fakten die Reihe der Tests zu konstruieren. Das Element x ist selbsverständlich nicht bekannt! Es gibt nun prinzipielle Unterschiede, wie eine Testteilmenge gefunden werden darf: Wählt der Algorithmus die Tests nacheinander aus, und darf er die Information aller schon durchgeführten Tests benutzen, heißt er sequentiell. Müssen alle Tests auf einmal ausgewählt werden, ist er predeterminiert.1. Eine Grapheneigenschaft P ist eine Teilmenge von Graphen mit fester Eckenzahl n, invariant unter Graphenisomorphie. Für einen unbekannten Grpahen G mit n Ecken soll getestet werden, ob er die Eigenschaft P hat oder nicht. Die möglichen Tests sind Fragen der Form „Ist e Kante von G?”. Gibt es für alle sequentielle Algorithmen einen Graphen G, für den alle Kanten getestet werden müssen, um zu entscheiden, ist P evasiv. Für eine Menge von Eigenschaften (nämlich nichttriviale, monotone) wird Evasivität vermutet. Bewiesen ist das für Primzahlpotenzen n=p^k (Kahn et al.). Jedoch gibt es allgemein nur eine asymptotische Abschätzung für die Anzahl der minimal nötigen Tests mit dieser Methode. Ich zeige eine Verbesserung dieser Abschätzung durch geschickte Anwendung einer topologischen Methode, sowie ein Resultat, dass den Einsatz von Computern bei diesem Problem illustriert.2. Bei einem Gruppentestproblem P wird in einer Menge X nach einer Teilmenge D gesucht. Getestet werden dürfen spezielle Teilmengen Y von X. Man erhält dabei Antwort auf die Frage „Ist D geschnitten Y nichtleer?”. Ist X die Menge der Kanten eines gegeben Graphen G, so sind in meinem Modell die wählbaren Teilmengen Y durch eine Auswahl an Ecken beschrieben. Es gibt eine auf Hypergraphen verallgemeinerte Vermutung (Du, Hwang), dass die Worst Case Komplexität c(P) des Problems in Abhängigkeit von der Kantenzahl |X| für eine davon unabhängige Konstante c beschreibt. Im Falle der Graphen existiert ein c. Ich gebe eine Vereinfachung des sequentiellen Algorithmus an, der dies beweist, und verbessere c. Weiterhin zeige ich, wo einige Probleme bei der Verallgemeinerung dieses Algorithmus auf Hypergraphen liegen.3. Man betrachtet den Gruppentest wie unter Punkt 2, aber mit nur einem zu suchenden Element: |D|=1. Weiterhin beschränkt man sich auf predeterminierte Algorithmen. In diesem Fall sind wenig gute Abschätzungen für c(P) bekannt, oder nur für sehr spezielle G. Im Falle dass G ein Baum ist, habe ich jedoch eine gute obere Schranke für c(P) zusammen mit einem konkreten Algorithmus gefunden. Der Beweis ist keineswegs trivial und, wie ich denke, eine sehr interessante Nutzung kombinatorischer und graphentheoretischer Begriffe. Die von mir vermutete optimale Schranke ist allerdings, wie ich zeige, so nicht beweisbar.

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.

Fulltext:
PDF
(additional files)