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, S-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.
 
This thesis investigates the parameterized computational complexity of

six classic graph problems lifted to a temporal setting. More

specifically, we consider problems defined on temporal graphs, that is, a

graph where the edge set may change over a discrete time interval,

while the vertex set remains unchanged. Temporal graphs are well-suited

to model dynamic data and hence they are naturally motivated in contexts

where dynamic changes or time-dependent interactions play an important

role, such as, for example, communication networks, social networks, or

physical proximity networks. The most important selection criteria for

our problems was that they are well-motivated in the context of dynamic

data analysis.Since temporal graphs are mathematically more complex than static

graphs, it is maybe not surprising that all problems we consider in this

thesis are NP-hard. We focus on the development of exact algorithms,

where our goal is to obtain fixed-parameter tractability results, and

refined computational hardness reductions that either show NP-hardness

for very restricted input instances or parameterized hardness with

respect to "large" parameters. In the context of temporal graphs, we

mostly consider structural parameters of the underlying graph, that is,

the graph obtained by ignoring all time information. However, we also

consider parameters of other types, such as ones trying to measure how

fast the temporal graph changes over time. In the following we briefly

discuss the problem setting and the main results.Restless Temporal Paths. A path in a temporal graph has to respect

causality, or time, which means that the edges used by a temporal path

have to appear at non-decreasing times. We investigate temporal paths

that additionally have a maximum waiting time in every vertex of the

temporal graph. Our main contributions are establishing NP-hardness for

the problem of finding restless temporal paths even in very restricted

cases, and showing W[1]-hardness with respect to the feedback vertex

number of the underlying graph.Temporal Separators. A temporal separator is a vertex set that, when

removed from the temporal graph, destroys all temporal paths between two

dedicated vertices. Our contribution here is twofold: Firstly, we

investigate the computational complexity of finding temporal separators

in temporal unit interval graphs, a generalization of unit interval

graphs to the temporal setting. We show that the problem is NP-hard on

temporal unit interval graphs but we identify an additional restriction

which makes the problem solvable in polynomial time. We use the latter

result to develop a fixed-parameter algorithm with a

"distance-to-triviality" parameterization. Secondly, we show that

finding temporal separators that destroy all restless temporal paths is

S-P-2-hard.Temporal Matchings. We introduce a model for matchings in temporal

graphs, where, if two vertices are matched at some point in time, then

they have to "recharge" afterwards, meaning that they cannot be matched

again for a certain number of time steps. In our main result we employ

temporal line graphs to show that finding matchings is NP-hard even on

instances where the underlying graph is a path.Temporal Coloring. We lift the classic graph coloring problem to the

temporal setting. In our model, every edge has to be colored properly

(that is, the endpoints are colored differently) at least once in every

time interval of a certain length. We show that this problem is NP-hard

in very restricted cases, even if we only have two colors. We present

simple exponential-time algorithms to solve this problem. As a main

contribution, we show that these algorithms presumably cannot be

improved significantly.Temporal Cliques and s-Plexes. We propose a model for temporal s-plexes

that is a canonical generalization of an existing model for temporal

cliques. Our main contribution is a fixed-parameter algorithm that

enumerates all maximal temporal s-plexes in a given temporal graph,

where we use a temporal adaptation of degeneracy as a parameter.Temporal Cluster Editing. We present a model for cluster editing in

temporal graphs, where we want to edit all "layers" of a temporal graph

into cluster graphs that are sufficiently similar. Our main contribution

is a fixed-parameter algorithm with respect to the parameter "number of

edge modifications" plus the "measure of similarity" of the resulting

clusterings. We further show that there is an efficient preprocessing

procedure that can provably reduce the size of the input instance to be

independent of the number of vertices of the original input instance.