Graph complexity measures and monotonicity

  • Komplexitätsmaße für Graphen und die Monotonie

Rabinovich, Roman; Grädel, Erich (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2013, 2014)
Doktorarbeit

Aachen, Techn. Hochsch., Diss., 2013

Kurzfassung

Strukturelle Komplexität von Instanzen schwerer Berechnungsprobleme war ein wichtiger Forschungsbereich in den letzten Jahrzehnten, dessen Erfolg sich unter anderem in im Begriff der Baumweite, eines Maßes für die strukturelle Komplexität für ungerichtete Graphen, manifestierte. Viele praktisch relevante, aber im Allgemeinen schwer zu lösende Probleme lassen sich auf Graphen mit beschränkter Baumweite effizient lösen. Für gerichtete Graphen gibt es verschiedene Maße, unter anderen das Entanglement, die gerichtete Baumweite, die DAG-Weite und die Kelly-Weite, die sowohl Vor- als auch Nachteile aufweisen. In der vorliegenden Dissertation studieren wir die Komplexitätsmaße, die als Suchspiele auf Graphen beschrieben werden können. Ein solches Suchspiel wird von einem Team von Polizisten, das einen Räuber zu fangen versucht. Genaue Spielregel definieren ein Spiel und dadurch ein Komplexitätsmaß: die Komplexität eines Graphen ist die minimale Anzahl von Polizisten, die man braucht, um den Räuber auf diesem Graphen zu fangen. Ein wichtiger Aspekt ist dabei die Monotonie, eine Eigenschaft der Gewinnstrategien für die Polizisten, welche die Existenz von Zerlegungen des gegebenen Graphen impliziert. Diese Zerlegungen erlauben die Konstruktion von effizienten Algorithmen für algorithmisch schwere Probleme auf den Graphen. Wir untersuchen verschiedene Eigenschaften, die mit der Monotonie verbunden sind und entwickeln Methoden, die es erlauben, mit der Monotonie zu arbeiten. Im ersten Teil befassen wir uns mit dem Spiel, das Entanglement definiert. Obwohl die Polizisten im Allgemeinen keine Gewinnstrategien haben, die im üblichen Sinne monoton wären, zeigen wir, dass das Spiel eine schwache Variante der Monotonie erlaubt. Daraus ergibt sich die Existenz von entsprechenden Zerlegungen des Graphen. Der zweite Teil ist dem Zusammenhang zwischen struktureller Komplexität und imperfekten Information gewidmet. Imperfekte Information ist ein mächtiges Mittel, das die Ausdrucksstärke von Spielen als Formalisierungsmethode erweitert. Das technisch anspruchsvollste Resultat dabei ist, dass Paritätsspiele mit imperfekter Information auf Graphklassen mit beschränkter DAG-Weite effizient lösbar sind. Der Beweis benutzt im hohem Maße den Begriff der Spiele mit mehreren Räubern. Wir entwickeln die Technik der verzögerten Polizistenplatzierung für Strategietransformationen. Die entscheidende Frage ist, ob die Monotoniekosten, also die Anzahl der zusätzlichen Polizisten, die man braucht, um den Räuber monoton zu fangen, mit einer Konstante beschränkt werden können. Wir analysieren das einzige bekannte Beispiel von Kreutzer und Ordyniak, das zeigt, dass die Monotoniekosten für die DAG-Weite positiv sein können. Wir definieren die schwache Monotonie und untersuchen das Problem der Beschränkheit der Monotoniekosten. Weiterhin definieren wir eine Zerlegung der Graphen, die einer Gewinnstrategie für die Polizisten in einem Spiel mit schwacher Monotonie entspricht. Der letzte Teil enthält eine Übersicht von bekannten Resultaten, die mit Beschränktheit der Maßwerte verschiedener Maßen auf denselben Graphklassen verbunden sind.

Identifikationsnummern