Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-5011
Main Title: Nowhere dense classes of graphs
Subtitle: characterisations and algorithmic meta-theorems
Translated Title: Nowhere Dense Klassen von Graphen
Translated Subtitle: Charakterisierungen und algorithmische Meta-Sätze
Author(s): Siebertz, Sebastian
Referee(s): Kreutzer, Stephan
Ossona de Mendez, Patrice
Král’, Daniel
Type: Doctoral Thesis
Language Code: en
Abstract: We show that every first-order property of graphs can be decided in almost linear time on every nowhere dense class of graphs. For graph classes closed under taking subgraphs, our result is optimal (under a standard complexity theoretic assumption): it was known before that for all classes C of graphs closed under taking subgraphs, if deciding first-order properties of graphs in C is fixed-parameter tractable, parameterized by the length of the input formula, then C must be nowhere dense. Nowhere dense graph classes form a large variety of classes of sparse graphs including the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs and graph classes of bounded expansion. For our proof, we provide two new characterisations of nowhere dense classes of graphs. The first characterisation is in terms of a game, which explains the local structure of graphs from nowhere dense classes. The second characterisation is by the existence of sparse neighbourhood covers. On the logical side, we prove a rank-preserving version of Gaifman's locality theorem. The characterisation by neighbourhood covers is based on a characterisation of nowhere dense classes by generalised colouring numbers. We show several new bounds for the generalised colouring numbers on restricted graph classes, such as for proper minor closed classes and for planar graphs. Finally, we study the parameterized complexity of the first-order model-checking problem on structures where an ordering is available to be used in formulas. We show that first-order logic on ordered structures as well as on structures with a successor relation is essentially intractable on nearly all interesting classes. On the other hand, we show that the model-checking problem of order-invariant monadic second-order logic is tractable essentially on the same classes as plain monadic second-order logic and that the model-checking problem for successor-invariant first-order logic is tractable on planar graphs.
Wir zeigen, dass jede Eigenschaft von Graphen aus einer nowhere dense Klasse von Graphen, die in der Präadikatenlogik formuliert werden kann, in fast linearer Zeit entschieden werden kann. Dieses Ergebnis ist optimal für Klassen von Graphen, die unter Subgraphen abgeschlossen sind (unter einer Standardannahme aus der Komplexitätstheorie). Um den obigen Satz zu beweisen, führen wir zwei neue Charakterisierungen von nowhere dense Klassen von Graphen ein. Zunächst charakterisieren wir solche Klassen durch ein Spiel, das die lokalen Eigenschaften von Graphen beschreibt. Weiter zeigen wir, dass eine Klasse, die unter Subgraphen abgeschlossen ist, genau dann nowhere dense ist, wenn alle lokalen Nachbarschaften von Graphen der Klasse dünn überdeckt werden können. Weiterhin beweisen wir eine erweiterte Version von Gaifman's Lokalitätssatz für die Prädikatenlogik, der eine Übersetzung von Formeln in lokale Formeln des gleichen Ranges erlaubt. In Kombination erlauben diese neuen Charakterisierungen einen effizienten, rekursiven Lösungsansatz für das Model-Checking Problem der Prädikatenlogik. Die Charakterisierung der nowhere dense Graphklassen durch die oben beschriebenen Überdeckungen basiert auf einer bekannten Charakterisierung durch verallgemeinerte Färbungszahlen. Unser Studium dieser Zahlen führt zu neuen, verbesserten Schranken für die verallgemeinerten Färbungszahlen von nowhere dense Klassen von Graphen, insbesondere für einige wichtige Subklassen, z. B. für Klassen mit ausgeschlossenen Minoren und für planare Graphen. Zuletzt untersuchen wir, welche Auswirkungen eine Erweiterung der Logik durch Ordnungs- bzw. Nachfolgerrelationen auf die Komplexität des Model-Checking Problems hat. Wir zeigen, dass das Problem auf fast allen interessanten Klassen nicht effizient gelöst werden kann, wenn eine beliebige Ordnungs- oder Nachfolgerrelation zum Graphen hinzugefügt wird. Andererseits zeigen wir, dass das Problem für ordnungsinvariante monadische Logik zweiter Stufe auf allen Klassen, für die bekannt ist, dass es für monadische Logik zweiter Stufe effizient gelöst werden kann, auch effizient gelöst werden kann. Wir zeigen, dass das Problem für nachfolgerinvariante Prädikatenlogik auf planaren Graphen effizient gelöst werden kann.
URI: http://depositonce.tu-berlin.de/handle/11303/5326
http://dx.doi.org/10.14279/depositonce-5011
Exam Date: 25-Sep-2015
Issue Date: 2016
Date Available: 24-May-2016
DDC Class: DDC::500 Naturwissenschaften und Mathematik::510 Mathematik::510 Mathematik
DDC::000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::005 Computerprogrammierung, Programme, Daten
Subject(s): graph theory
parameterized complexity theory
finite model theory
algorithmic graph structure theory
first-order logic
Meta-Theorems
Graphentheorie
parametrisierte Komplexitätstheorie
endliche Modelltheorie
algorithmische Graphentheorie
Prädikatenlogik
Meta-Sätze
Creative Commons License: https://creativecommons.org/licenses/by/4.0
Series: Foundations of computing
Series Number: 5
EISSN: 2199-5257
ISBN: 978-3-7983-2819-8
ISSN: 2199-5249
Notes: Published in print by Universitätsverlag der TU Berlin, ISBN 978-3-7983-2818-1 (ISSN 2199-5249)
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 4 Elektrotechnik und Informatik » Institut für Softwaretechnik und Theoretische Informatik » Publications

Files in This Item:
File Description SizeFormat 
siebertz_sebastian.pdf2.67 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.