About Treedepth and Related Notions

Sanchez Villaamil, Fernando; Rossmanith, Peter; Fernau, Henning

doi:10.18154/RWTH-2017-09829

About Treedepth and Related Notions

Sanchez Villaamil, Fernando

2017 & 2018

Verantwortlichkeitsangabevorgelegt von Diplom-Informatiker Fernando Sánchez Villaamil

ImpressumAachen 2017

Umfang1 Online-Ressource (getrennte Zählung) : Illustrationen

Dissertation, RWTH Aachen University, 2017

Veröffentlicht auf dem Publikationsserver der RWTH Aachen University 2018

Genehmigende Fakultät
Fak01

Hauptberichter/Gutachter
Rossmanith, Peter (Thesis advisor) ; Fernau, Henning (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2017-11-10

Online
DOI: 10.18154/RWTH-2017-09829
URL: https://publications.rwth-aachen.de/record/709271/files/709271.pdf

Einrichtungen

Inhaltliche Beschreibung (Schlagwörter)
dynamic programming (frei) ; motif counting (frei) ; random intersection graphs (frei) ; space complexity (frei) ; treedepth (frei) ; treewidth (frei)

Thematische Einordnung (Klassifikation)
DDC: 004

Kurzfassung
In dieser Doktorarbeit stellen wir verschiedene Ergebnisse in Bezugauf Baumtiefe vor. Als Erstes liefern wir den schnellsten Linearzeit-fpt-Algorithmus, um die Baumtiefe eines Graphen zuberechnen. Er entscheidet, ob ein Graph Baumtiefe d in 2^O(d^2) n Schritten hat. Dabei beantworten wir eine offene Frage von Nešetřil und Ossona de Mendez, in der nach einem einfachen Linearzeit-fpt-Algorithmus gefragt wurde. Als Nächstes vergleichen wir Baumweite und Baumtiefe. Wir beweisen untere Schranken für die Laufzeit und den Platzverbrauch von dynamicprogramming-Algorithmen (auf der Basis einer sinnvollen Definition voneinem dynamic programming-Algorithmus) für Vertex Cover, 3-Coloringund Dominating Set auf einer Baum-, Pfad- oder Baumtiefenzerlegung. Diese Schranken stimmen mit den besten Laufzeiten von bekannten Algorithmen für diese Probleme überein. Es ist nicht schwierig, sich davon zu überzeugen, dass man Vertex Cover und 3-Coloring, parametrisiert mit einer gegebenen Baumtiefenzerlegung mit Tiefe $d$, mit einem Platzverbrauch von poly(d) log n lösen kann. Wir zeigen, dass das Gleiche für Dominating Set möglich ist. Wir analysieren das random intersection graph-Modell, das versucht, Netzwerke zu modellieren, bei denen Verbindungen gemeinsame Attribute der Knoten darstellen. Wir zeigen, dass dieses Modell, derartkonfiguriert, dass es degenerierte Graphen erzeugt, mit hoher Wahrscheinlichkeit Graphen generiert, die zu einer boundedexpansion-Graphklasse gehören. Weiterhin beweisen wir, dass dieses Modell auf andere Weise konfiguriert, Graphen erzeugt, die asymptotisch fast sicher somewhere dense sind. Wir stellen dann einen Algorithmus für motif/subgraph counting auf bounded expansion-Graphenvor, der eine Charakterisierung von bounded expansion-Graphklassen mittels einer Dekomposition des Graphen in Teilen mit beschränkter Baumtiefe ausnutzt. Zuletzt beschreiben wir eine Heuristik, die zuerst eine Baumtiefenzerlegung und daraus eine Baumzerlegung des Graphen berechnet. Wir zeigen, dass diese mit anderen bekannten Heuristiken für Baumzerlegungen konkurrieren kann.

In this thesis we present several results relating to treedepth. First, we provide the fastest linear-time fpt algorithm to compute the treedepth of a graph. It decides if a graph has treedepth d in time 2^O(d^2) n. In the process we answer an open question by Nešetřil and Ossona de Mendez, which asked for a simple linear-time fpt algorithm.We then proceed to compare treewidth to treedepth. We give lower bounds for the running time and space consumption of any dynamic programming algorithm (for a reasonable definition of dynamic programming on tree/path/treedepth decompositions which we introduce) for the problems Vertex Cover, 3-Coloring and Dominating Set on either a tree, a path or a treedepth decomposition. These bounds match the best known running times for these problems to date. It is not difficult to see that there are linear-time fpt algorithms for Vertex Cover and 3-Coloring parameterized by a given treedepth decomposition of depth d with a space consumption bounded by poly(d) log n. We show the same is possible for Dominating Set. We analyze the random intersection graph model, which attempts to model real-world networks where the connections between actors represent underlying shared attributes. We show that this model, when configured such that it generates degenerate graphs, produces with high probability graphs which belong to a class of bounded expansion, otherwise the graphs are asymptotically almost surely somewhere dense. We then present an algorithm for motif/subgraph counting on bounded expansion graphs which exploits a characterization of bounded expansion graph classes via decompositions into parts of bounded treedepth. Finally, we present a heuristic to compute tree decompositions which starts by computing a treedepth decomposition and show that it is competitive against other known heuristics.

OpenAccess:
PDF
(additional files)