Graph complexity measures and monotonicity

Rabinovich, Roman; Grädel, Erich

doi:4808

Graph complexity measures and monotonicity = Komplexitätsmaße für Graphen und die Monotonie

Rabinovich, Roman (Author)

2013 & 2014

Verantwortlichkeitsangabevorgelegt von Roman Rabinovich

ImpressumAachen : Publikationsserver der RWTH Aachen University 2013

Umfang163 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2013

Zsfassung in dt. und engl. Sprache. - Prüfungsjahr: 2013. - Publikationsjahr: 2014

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Grädel, Erich (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2013-02-19

Online
URN: urn:nbn:de:hbz:82-opus-48083
URL: https://publications.rwth-aachen.de/record/230227/files/4808.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
Komplexität (Genormte SW) ; Gerichteter Graph (Genormte SW) ; Baumweite (Genormte SW) ; Spiel in extensiver Form (Genormte SW) ; Informatik (frei) ; Strukturelle Komplexität (frei) ; Graph-Searching-Spiel (frei) ; DAG-Weite (frei) ; Treewidth (frei) ; structural complexity (frei) ; graph searching game (frei) ; DAG-width (frei) ; monotonicity (frei) ; tree width (frei)

Thematische Einordnung (Klassifikation)
DDC: 004
msc: 05C57

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.

The structural complexity of instances of computational problems has been an important research area in theoretical computer science in the last decades. Its success manifested itself in tree-width - a complexity measure for undirected graphs. Many practically relevant problems that are difficult in general, can be efficiently solved on graphs of bounded tree-width. For directed graphs, there are several similar measures, among others entanglement, directed tree-width, DAG-width and Kelly-width, that have shown their advantages as well as disadvantages. In this thesis, we work on complexity measures for directed graphs that can be described in terms of graph searching games. A graph searching game is played on a given graph by a team of cops and a robber. The cops try to capture the robber whose intent is to escape. Precise rules define a game and a complexity measure on graphs. The complexity of a graph is usually the minimal number of cops needed to capture the robber. Hereby, an important issue is monotonicity, a property of winning cop strategies. It implies the existence of suitable decompositions of the given graphs which allow for efficient algorithms for difficult computational problems. We discuss monotonicity issues of graph searching games, discuss problems appearing when monotonicity is introduced, and develop methods for solving those problems. In the first part, we consider the game defining entanglement. While, in general, there are no monotone winning strategies for the cops in the usual sense, we prove a weak variant of monotonicity for two cops. This implies the existence of corresponding graph decompositions. The second part is dedicated to the relationship between structural complexity and imperfect information. The latter is a powerful tool to extend expressiveness of games. The most involved result in that part is that parity games with bounded imperfect information can be efficiently solved on classes of directed graphs of bounded DAG-width. Its proof heavily relies on a notion of games with multiple robbers. We develop the technique of omitting cop placements while transforming strategies. The crucial question about monotonicity is whether monotonicity costs, the number of additional cops needed to capture the robber monotonically, can be bounded by a constant. We analyse the only known example by Kreutzer and Ordyniak which shows that the monotonicity costs for DAG-width can be positive. We define a notion of weak monotonicity for DAG-width and investigate the problem of boundedness of weak monotonicity costs. Furthermore, we define a structural decomposition of graphs that corresponds to a winning cop strategy in a game with weak monotonicity. The last part gives an overview of known results concerning boundedness of values of different measures on the same graph classes.

Fulltext:
PDF