Classic graph problems made temporal – a parameterized complexity analysis

In dieser Dissertation untersuchen wir die parametrisierte
Berechnungskomplexität von sechs klassischen Graphproblemen, die in
einen temporalen Kontext gestellt werden. Formaler ausgedrückt
betrachten wir Probleme, die auf temporalen Graphen definiert sind,
wobei temporale Graphen aus einer unveränderlichen Knotenmenge bestehen,
zusammen mit einer Kantenmenge, die sich über einen diskreten Zeitraum
hinweg verändern darf. Temporale Graphen eignen sich besonders gut zum
Modellieren dynamischer Daten und sind daher in Situationen von
Bedeutung, in denen dynamische Veränderungen oder zeitabhängige
Interaktionen eine wichtige Rolle spielen. Beispiele hierfür sind das
Betrachten von Kommunikationsnetzwerken, sozialen Netzwerken oder
Netzwerken, deren Interaktionen räumliche Annäherungen modellieren. Das
wichtigste Auswahlkriterium für unsere Problemstellungen war, dass sie
in Kontexten der Analyse dynamischer Daten wohlmotiviert sind.
Da temporale Graphen mathematisch gesehen komplexer sind als statische
Graphen, ist es vielleicht nicht sehr überraschend, dass alle Probleme,
die wir in dieser Dissertation betrachten, NP-schwer sind. Wir
konzentrieren uns auf die Entwicklung exakter Algorithmen, wobei wir
versuchen FPT-Resultate zu erzielen oder durch spezialisierte
Reduktionen zu zeigen, dass das betrachtete Problem NP-schwer auf sehr
eingeschränkten Instanzen ist, oder berechnungsschwer im
parametrisierten Sinne bezüglich möglichst „großer“ Parameter ist. Im
Kontext temporaler Graphen betrachten wir in erster Linie
Strukturparameter des unterliegenden Graphen, das heißt des Graphen, den
man erhält, wenn man alle Zeitinformationen ignoriert. Allerdings
studieren wir auch andere Parameter, zum Beispiel solche, die das Ausmaß
der zeitlichen Veränderung eines temporalen Graphen messen. Im
Folgenden geben wir einen kurzen Überblick über unsere Problemstellungen
und wichtigsten Ergebnisse.
Restless Temporal Paths. Ein Pfad in einem temporalen Graph muss
Kausalität oder Zeit respektieren. Dies bedeutet, dass die Kanten, die
von dem temporalen Pfad benutzt werden, nicht zu abnehmenden Zeitpunkten
erscheinen dürfen. Wir untersuchen temporale Pfade, die darüber hinaus
eine maximal erlaubte Wartezeit in allen Knoten haben. Unsere
Hauptresultate sind, dass Pfade dieser Art zu finden NP-schwer ist,
sogar in sehr restriktiven Instanzen, und dass das Problem W[1]-schwer
bezüglich der kreiskritischen Knotenzahl des unterliegenden Graphen ist.
Temporal Separators. Ein temporaler Separator ist eine Knotenmenge, die,
wenn sie aus einem temporalen Graph entfernt wird, alle temporalen
Pfade zwischen zwei iausgewählten Knoten zerstört. Wir erzielen hier
zwei Hauptresultate: Auf der einen Seite untersuchen wir die
Berechnungskomplexität des Findens von temporalen Separatoren in
temporalen Einheitsintervallgraphen, einer Verallgemeinerung von
Einheitsintervallgraphen im temporalen Kontext. Wir zeigen, dass das
Problem auf temporalen Einheitsintervallgraphen NP-schwer ist, aber
identifizieren eine weitere Einschränkung, die es erlaubt, das Problem
in Polynomzeit zu lösen. Auf Letzterem aufbauend entwickeln wir einen
FPT-Algorithmus, der eine „Distanz-zur-Trivialität“-Parametrisierung
nutzt. Auf der anderen Seite zeigen wir, dass das Finden temporaler
Separatoren, die alle ruhelosen temporalen Pfade zerstören, Σ-P-2-schwer
ist.
Temporal Matchings. Wir führen ein Modell für Matchings in temporalen
Graphen ein, bei dem sich zwei Knoten „erholen“ müssen, nachdem sie zu
einem bestimmten Zeitpunkt einander zugeordnet wurden. Das heißt, für
eine gewisse Zeit können diese Knoten nicht wieder einander zugeordnet
werden. Wir nutzen das Konzept von temporalen Kantengraphen, um zu
zeigen, dass das Finden von temporalen Matchings NP-schwer ist, selbst
wenn der unterliegende Graph ein Pfad ist.

Temporal Coloring. Wir übertragen das klassische Knotenfärbungsproblem
in den temporalen Rahmen. In unserem Modell muss jede Kante in jedem
Zeitfenster einer bestimmten Größe mindestens einmal gültig gefärbt
sein, also beide Endpunkte eine andere Farbe haben. Wir zeigen, dass
dieses Problem schon auf sehr eingeschränkten Instanzen NP-schwer ist –
sogar für zwei Farben. Wir beschreiben einfache
Exponentialzeitalgorithmen für dieses Problem. Eines unserer
Hauptresultate ist, dass diese Algorithmen vermutlich nicht signifikant
verbessert werden können.
Temporal Cliques and s-Plexes. Wir stellen ein Modell für temporale
s-Plexe vor, das eine kanonische Verallgemeinerung eines existierenden
Modells für temporale Cliquen ist. Unser Hauptresultat ist ein
FPT-Algorithmus, der alle maximalen temporalen s-Plexe aufzählt, wobei
wir eine temporale Variante von Degeneriertheit von Graphen als
Parameter benutzen.
Temporal Cluster Editing. Wir stellen ein Modell für Clustereditierung
in temporalen Graphen vor, bei dem wir alle „Schichten“ eines temporalen
Graphens in hinreichend ähnliche Cluster überführen wollen. Unsere
Hauptergebnisse sind zum einen ein FPT-Algorithmus bezüglich des
Parameters „Anzahl der Editierungen plus Ähnlichkeit der Cluster“. Zum
anderen geben wir eine effiziente Vorverarbeitungsmethode an, welche die
Größe der Eingabeinstanz beweisbar so reduziert, dass sie unabhängig
von der Anzahl der Knoten der ursprünglichen Instanz ist.