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)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2008

Kurzfassung

Angenommen, wir suchen nach einer unbekannten Kante $e$ in einem gegebenen Graph $G(V,E)$. Um die Endknoten der Kante $e$ zu finden, waehlen wir eine Teilmenge $X$ von $V$ der Kardinalität höchstens $p$ und stellen Fragen der Form: "Ist mindestens einer der Knoten von $X$ ein Endknoten von $e$?". Was ist dann die minimale Anzahl $c_p(G)$ von Fragen die notwendig sind, um $e$ im schlimmstmoeglichen Fall zu bestimmen? In der vorliegenden Arbeit lösen wir das Problem durch die Herleitung unterer Schranken und einer scharfen oberen Schranke für die $p$-Komplexität $c_p(G)$. Wir zeigen ausserdem, dass das Entscheidungsproblem, ob $c_p(G)leq k$ für eine gegebene natürliche Zahl $k$ gilt, NP-vollstaendig ist für jede natürliche Zahl $p$. Wir gehen speziell auf die Analyse der Greedy-Strategie ein und zeigen, dass das Entscheidungsproblem, ob die Anzahl der benötigten Fragen kleiner oder gleich $k$ ist, sogar dann NP-vollständig bleibt, wenn man diese einfache Strategie benutzt. Des weiteren nehmen wir eine probabilistische Analyse der Greedy-Schranke vor. Für den Fall, dass $G$ ein vollständiger Graph ist, ist das oben beschriebene Problem aequivalent zu dem $(2,n)$-Gruppentestproblem mit Testmengen der Kardinalitaet höchstens $p$. Wir präsentieren scharfe untere und obere Schranken für die Komplexität dieses Gruppentestproblems und zeigen, dass die maximale Differenz zwischen diesen beiden Schranken 3 beträgt. Wir gehen darüberhinaus ausführlich auf den gut erfassbaren Fall $p=2$ ein und geben $c_2(G)$ für gewisse Graphenklassen exakt an. Wir beweisen eine scharfe obere Schranke für die Anzahl der Kanten in einem Graphen in Abhängigkeit von $c_2(G)$ und leiten daraus eine scharfe untere Schranke für $c_2(G)$ ab. Die Graphen, für die Gleichheit gilt, werden auf unterschiedliche Weisen charakterisiert, und wir vermuten, dass diese Charakterisierung benutzt werden kann, um für solche Graphen einen polynomiellen Algorithmus zur Berechnung von $c_2(G)$ zu konstruieren. Außerdem leiten wir eine scharfe obere Schranke für $c_2(G)$ her und geben notwendige und hinreichende Bedingungen an Graphen für das Annehmen dieser oberen Schranke an.